HDOJ(HDU).1015 Safecracker (DFS)

2019-11-11 07:53:46

字體：大中小

來源：轉載

供稿：網友

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)] —小結：做DFS題目的關注點 HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習 HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習/check函數的思想

題意分析

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

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

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

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

Tip:B明顯比V小

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

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循環來實現。

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

代碼總覽

/* 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函數中完成了數據的讀入，init函數把字符數組a中的字母轉變成數字，lnit函數在最后輸出的時候把數組b中的答案又轉變成了字母，check函數就是檢查是否是滿足題目要求的解。關鍵在dfs函數。

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

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

上一篇：1045. 快速排序(25)

下一篇：ChucK初步（6）