- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。 - 输入
- 第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用'.'表示，有障碍物的格子用'#'表示。
迷宫左上角和右下角都是'.'。 - 输出
- 输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
- 样例输入
-
5 5 ..### #.... #.#.# #.#.# #.#..
- 样例输出
-
9
、、虽然水了点但为了为走上歧途的同学解答
还是写了题解，这大概是第一次写dfs的题解。。。。。
首先看到这题的第一反应不应该是dfs（反正我第一个想到的是dp）
不过既然要dfs的
那就好好看看吧
首先发现数据十分水
所以不要记忆化
不要记忆化的代码是令人愉悦的
所以就开动了
首先是状态数组，bool b【】【】
把‘’0‘’作为‘’墙‘’
在输入时直接处理好
然后我们发现可以上下左右乱爬
那写四个if？？？？
我有点恐惧，所以最好使用方向数组mapp【】【】
做好可爱的回溯后就是简单的优化
比如当我们发现k（目前步数）已经大于记录的最小步了
那就直接give out it！
所以。。。。上代码吧#include<bits/stdc++.h> using namespace std; char c; int ans=0x7fffff,m,n; bool b[1000][1000]; int mapp[3][5]; void dfs(int x,int y,int k) { if(x==m&&y==n) { ans=min(ans,k); return ; } if(k>ans) return ; for(int i=1;i<=4;i++) { if(b[x+mapp[1][i]][y+mapp[2][i]]==1){ b[x+mapp[1][i]][y+mapp[2][i]]=0; dfs(x+mapp[1][i],y+mapp[2][i],k+1); b[x+mapp[1][i]][y+mapp[2][i]]=1; } } } int main() { cin>>m>>n; mapp[1][1]=-1;mapp[2][1]=0; mapp[1][2]=1;mapp[2][2]=0; mapp[1][3]=0;mapp[2][3]=1; mapp[1][4]=0;mapp[2][4]=-1; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){ cin>>c; if(c=='#') b[i][j]=0; else b[i][j]=1; } dfs(1,1,1); cout<<ans; }
//终于水完这题了。。。
//恩，那就这样吧。。。。（表示懒，不想记忆化）