题解P1605 迷宫
Ryo_Yamada
2019-11-09 07:08:57
迷宫这系列的题算是dfs最经典的题了吧。
窝看到有一些dl用map标记，这里就给没学过map的提供一种做法。
我们用一个char数组记录障碍和起点。
```cpp
char c[6][6];
```
```cpp
if(c[sx][sy] == 'T'){
cnt++;
return;
}//标记终点
```
```cpp
for(int i=0; i<t; i++){
int zx,zy;
cin >> zx >> zy;
c[zx - 1][zy - 1] = '#';
}//标记障碍
```
最后是我~~可爱~~的代码君：
```cpp
#include <iostream>
using namespace std;
char c[6][6];
int cnt;
int dir[4][2] = {
{1,0},
{0,1},
{-1,0},
{0,-1}
};//下一步
int n,m;
bool vis[6][6];//记录是否走过
bool in(int sx, int sy){//是否在地图内
return sx >= 0 && sx < n && sy >= 0 && sy < m;
}
void dfs(int sx, int sy){//深搜
vis[sx][sy] = true;
if(c[sx][sy] == 'T'){
cnt++;
return;
}//如果是终点，计数++，返回
for(int i=0; i<4; i++){
int tx = sx + dir[i][0];
int ty = sy + dir[i][1];//记录下一步的坐标
if(in(tx,ty) && !vis[tx][ty] && c[tx][ty] != '#'){//判断递归条件
vis[tx][ty] = true;//标记
dfs(tx,ty);//递归搜索
vis[tx][ty] = false;//尝试回溯
}
}
return;
}
int main(){
int t;
cin >> n >> m >> t;
int sx,sy,fx,fy;
cin >> sx >> sy >> fx >> fy;
c[fx - 1][fy - 1] = 'T';
for(int i=0; i<t; i++){
int zx,zy;
cin >> zx >> zy;
c[zx - 1][zy - 1] = '#';
}
dfs(sx - 1,sy - 1);//搜索，如果像我一样喜欢由0开头，需要-1
cout << cnt;//输出
return 0;
}完结撒花
```
希望能帮到大家，最后祝大家AC此题