HDOJ(HDU).1015 Safecracker (DFS)

2019-11-14 09:19:12

字體：大中小

供稿：網(wǎng)友

HDOJ(HDU).1015 Safecracker [從零開始DFS(2)]

從零開始DFS HDOJ.1342 Lotto [從零開始DFS(0)] — DFS思想與框架/雙重DFS HDOJ.1010 Tempter of the Bone [從零開始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [從零開始DFS(2)] —DFS四向搜索變種 HDOJ(HDU).1016 PRime Ring Problem (DFS) [從零開始DFS(3)] —小結(jié)：做DFS題目的關(guān)注點 HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習(xí)/check函數(shù)的思想

題意分析

首先默認有個字母到數(shù)字的映射，A=1，B=2，C=3 …… Z=26,給出你一個目標(biāo)數(shù)字target，然后給出一串字母，要求從這些字母中選取5個數(shù)字vwxyz，滿足 v - w^2 + x^3 - y^4 + z^5 = target。可能有多組解，只輸出字典序最大的那個。

嗨呀一看到這道題，是否有種似曾相識的感覺。很像 HDOJ.1342 Lotto [從零開始DFS(0)]這道題。題目的大意都是選數(shù)字，滿足某種要求。我們分析一下這道題和HDOJ.1342的異同：

1.HDOJ.1342給出的數(shù)據(jù)是有序的因此我們直接想選擇/不選，找到解的時候就直接是按照字典序由小到大輸出的。但是本題給出來的字母的序列是無序的因此想要只輸出一組字典序最大的解就需要按照降序排序，然后再處理。

2.HDOJ.1342中每個數(shù)字面臨的情況是選或者不選，只要位數(shù)湊夠6即可。但是此題不能按照這樣的想法，因為按照順序判定選或者不選的時候，這樣可能丟解。舉個例子：給定的字母序列（已經(jīng)按照降序排列好）：ZXVUNMDBA 按照之前的思路，我們只需要依次判定Z選/不選，X選/不選……A選/不選。把選定的5個數(shù)字依次填在v, w, x, y, z的位置上。但是如果 ZBVUN是一組解的話，按照上面的思路根本搜索不到。

Tip:B明顯比V小

解決方法：想起 HDOJ.1010 Tempter of the Bone [從零開始DFS(1)]中的4方向搜索的環(huán)節(jié)了嗎？只需要對dfs函數(shù)稍加改動，再用visit數(shù)組判斷是否選擇過此數(shù)字即可。

HDOJ.1010 中的四方向搜索：

for(int i = 0;i<4;++i){ if(!visit[x+spx[i]][y+spy[i]]&&!judge){ dfs(x+spx[i],y+spy[i],s+1); visit[x+spx[i]][y+spy[i]] = false; } }

Tip: 我們按照這樣式的，采用for循環(huán)來實現(xiàn)。

上代碼，掰開了揉碎了慢慢來。。

代碼總覽

/* HDOJ.1015 Author:pengwill Date:2017-2-5*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char a[15], b[10];int visit[15];int n,num,len;bool judge = false;bool cmp(char a, char b){ return a>b;}void init(){ len = strlen(a); judge = false; memset(visit,0,sizeof(visit)); sort(a,a+len,cmp); for(int i = 0;i<len;++i){ a[i] = a[i] -'A' + 1; }}void lnit(){ for(int i = 0;i<5;++i) b[i] = b[i]+'A'-1;}bool check(){ if(n == b[0] - b[1]*b[1] + b[2]*b[2]*b[2] - b[3]*b[3]*b[3]*b[3] + b[4]*b[4]*b[4]*b[4]*b[4]){ judge = true; return true; }else return false;}void dfs(int depth){ //遞歸邊界 if(judge) return; if(depth == 5) {check(); return;} for(int i = 0;i<len;++i){ if(!visit[i]&&!judge){ b[depth] = a[i]; visit[i] = 1; dfs(depth+1); visit[i] = 0; } }}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d %s",&n,a)&& !(n==0 && !strcmp(a,"END"))){ init(); dfs(0); lnit(); if(judge)printf("%s/n",b); else printf("no solution/n"); } return 0;}

main函數(shù)中完成了數(shù)據(jù)的讀入，init函數(shù)把字符數(shù)組a中的字母轉(zhuǎn)變成數(shù)字，lnit函數(shù)在最后輸出的時候把數(shù)組b中的答案又轉(zhuǎn)變成了字母，check函數(shù)就是檢查是否是滿足題目要求的解。關(guān)鍵在dfs函數(shù)。

void dfs(int depth){ //遞歸邊界 if(judge) return; if(depth == 5) {check(); return;} for(int i = 0;i<len;++i){ if(!visit[i]&&!judge){ b[depth] = a[i]; visit[i] = 1; dfs(depth+1); visit[i] = 0; } }}

不要忘記題目要求：找到一組字典序最大的解即可。首先是遞歸邊界，如果找到了解（judge為真），停止遞歸；亦或是當(dāng)depth為5（代表找到了5個數(shù)字）的時候，用check函數(shù)判斷一下是否滿足題目要求。若都不滿足遞歸邊界，繼續(xù)搜索。下面的for循環(huán)非常像dfs地圖的四向搜索，但是len指的是數(shù)據(jù)中給定的字母序列的長度。那么就指，下一個搜索的目標(biāo)要在所有的字母序列中找，哪些可以作為搜索目標(biāo)呢？首先就是這個字母沒有被選定過（!visit[i] ）并且現(xiàn)在解還沒有找到（!judge）。進入if后，首先把數(shù)組b中depth的位置賦值為a[i]，代表我數(shù)組b選定了你a中i這個位置的數(shù)字（或者說是字母）,并且在visit中置為選擇過了，dfs(depth+1)繼續(xù)尋找下一個位置的搜索目標(biāo)。別忘了最后把visit[i]置為0（無后效性）。

相比前邊2題，此題的收獲就在于：原先的地圖四向搜索，也可以變成這樣從幾個字符，數(shù)字中尋找可行的解。活學(xué)活用，非常重要呀！

上一篇：JDBC學(xué)習(xí)總結(jié)

下一篇：Spring mvc Interceptor 解決Session超時配置流程