对于深度优先算法,第一个直观的想法是只要是要求输出最短情况的详细步骤的题目基本上都要使用深度优先来解决。比较常见的题目类型比如寻路等,可以结合相关的经典算法进行分析。
常用步骤:
第一道题目:Dungeon Master http://poj.org/problem?id=2251
Input
The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
此题目只要求了求出最短的路径步骤,肯定适合使用广度优先算法来处理,但是如果再要求输出对应最短路径下的具体路径,则只能使用深度优先来处理了。
先来一个广度优先算法的参考代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cmath> 5 #include <cstring> 6 7 using namespace std; 8 9 int l,r,c; 10 11 struct node 12 { 13 int i; 14 int j; 15 int k; 16 int s; 17 }; 18 19 string road[30][30]; 20 int visited[30*30*30];//i*r*c+j*c+k为索引值 21 22 void getroad(int es) 23 { 24 int i,j,k; 25 node first,next; 26 bool flag=false; 27 28 for(i=0;i<l;i++) 29 { 30 for(j=0;j<r;j++) 31 { 32 for(k=0;k<c;k++) 33 { 34 if(road[i][j][k] == 'S')//找到初始点,标记 35 { 36 first.i=i; 37 first.j=j; 38 first.k=k; 39 first.s=0; 40 flag=true; 41 break; 42 } 43 } 44 if(flag) 45 break; 46 } 47 if(flag) 48 break; 49 } 50 51 queue<node> q; 52 q.push(first); 53 visited[first.i*r*c+first.j*c+first.k]=es; 54 55 while(!q.empty()) 56 { 57 first=q.front(); 58 q.pop(); 59 60 //需要设计上下左右前后6个方向,1维只有上下j左右k,2维以上再添加前后i 61 //同时需要考虑是否处在边界的情况 62 next=first; 63 next.s+=1; 64 int index=0; 65 66 next.j-=1;//上 67 index=next.i*r*c+next.j*c+next.k; 68 if(next.j>=0 && road[next.i][next.j][next.k] == '.') 69 { 70 if(visited[index] != es) 71 { 72 q.push(next); 73 visited[index]=es; 74 } 75 } 76 if(next.j>=0 && road[next.i][next.j][next.k] == 'E') 77 { 78 cout<<"Escaped in "<<next.s<<" minute(s)."<<endl; 79 return; 80 } 81 82 next.j+=2;//下 83 index=next.i*r*c+next.j*c+next.k; 84 //cout<<str[next.i][next.j][next.k]<<endl; 85 if(next.j<r && road[next.i][next.j][next.k] == '.') 86 { 87 if(visited[index] != es) 88 { 89 q.push(next); 90 visited[index]=es; 91 } 92 } 93 if(next.j<r && road[next.i][next.j][next.k] == 'E') 94 { 95 cout<<"Escaped in "<<next.s<<" minute(s)."<<endl; 96 return; 97 } 98 99 next.j-=1;//复原 100 101 next.k-=1;//左 102 index=next.i*r*c+next.j*c+next.k; 103 if(next.k>=0 && road[next.i][next.j][next.k] == '.') 104 { 105 if(visited[index] != es) 106 { 107 q.push(next); 108 visited[index]=es; 109 } 110 } 111 if(next.k>=0 && road[next.i][next.j][next.k] == 'E') 112 { 113 cout<<"Escaped in "<<next.s<<" minute(s)."<<endl; 114 return; 115 } 116 117 next.k+=2;//右 118 index=next.i*r*c+next.j*c+next.k; 119 if(next.k<c && road[next.i][next.j][next.k] == '.') 120 { 121 if(visited[index] != es) 122 { 123 q.push(next); 124 visited[index]=es; 125 } 126 } 127 if(next.k<c && road[next.i][next.j][next.k] == 'E') 128 { 129 cout<<"Escaped in "<<next.s<<" minute(s)."<<endl; 130 return; 131 } 132 133 next.k-=1;//复原 134 135 if(l>1) 136 { 137 next.i-=1;//前 138 index=next.i*r*c+next.j*c+next.k; 139 if(next.i>=0 && road[next.i][next.j][next.k] == '.') 140 { 141 if(visited[index] != es) 142 { 143 q.push(next); 144 visited[index]=es; 145 } 146 } 147 if(next.i>=0 && road[next.i][next.j][next.k] == 'E') 148 { 149 cout<<"Escaped in "<<next.s<<" minute(s)."<<endl; 150 return; 151 } 152 153 next.i+=2;//后 154 index=next.i*r*c+next.j*c+next.k; 155 if(next.i<l && road[next.i][next.j][next.k] == '.') 156 { 157 if(visited[index] != es) 158 { 159 q.push(next); 160 visited[index]=es; 161 } 162 } 163 if(next.i<l && road[next.i][next.j][next.k] == 'E') 164 { 165 cout<<"Escaped in "<<next.s<<" minute(s)."<<endl; 166 return; 167 } 168 } 169 } 170 cout<<"Trapped!"<<endl; 171 } 172 173 174 int main() 175 { 176 int count=1; 177 178 while(true) 179 { 180 cin>>l>>r>>c; 181 182 if(l==0 && r==0 && c==0) 183 break; 184 185 186 int i=0; 187 int j=0; 188 string tmp; 189 for(i=0;i<l;i++) 190 { 191 for(j=0;j<r;j++) 192 cin>>road[i][j]; 193 getline(cin,tmp); 194 } 195 getroad(count); 196 197 for(i=0;i<l;i++) 198 for(j=0;j<r;j++) 199 road[i][j].clear(); 200 201 count++; 202 } 203 204 return 0; 205 }
题目更改一下,要求输出最短步数,并且输出对应的具体路径。
考虑一下: