当然选择原谅她呀 DFS

Description

小陈和小白是一对恩爱的夫妻， 可是有一天小白被困在了大魔王小张的手里， 小张将小白困在了迷宫的最右下角，于是小陈打算从迷宫的左上角出发去找到她并且原谅她呀！

Input

输入文件将包含一组或者几组数据。每组测试数据包含一个n, m(0 < n,m <= 20)表示迷宫的行数和列数。紧跟着一个n行m列的矩阵表示一个迷宫， 其中的1表示墙壁，0表示可以走的路， 只能横着走或者竖着走， 不能斜着走， 要求编程序找出从左上角到右下角最短路径的步数。

Output

左上角到右下角最短路径的步数。如果小陈没办法原谅小陈， 输出”-1”

Sample Input

5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

Sample Output

8

Hint

题意

题解：

啦啦啦

AC代码

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int n,m,dis; int mp[25][25]; int to[4][2]={1,0,-1,0,0,1,0,-1}; void dfs(int x,int y,int temp){ mp[x][y] = 0; if (x == n&&y == m) { dis = min(dis,temp); return ; } int tx,ty; for (int i = 0; i < 4; ++i){ tx = x + to[i][0]; ty = y + to[i][1]; if (mp[tx][ty]){ dfs(tx,ty,temp+1); mp[tx][ty] = 1; /*回溯的目的 再有多条路到终点时 可以更新最短的路径 不这么做的话走一遍的路的距离就不会再更新了*/ } } } int main(){ while (~scanf("%d%d",&n,&m)){ memset(mp,0,sizeof(mp)); int xx; for (int i = 1; i <= n; ++i){ for (int j = 1; j <= m; ++j){ scanf("%d",&xx); mp[i][j] = !xx; } } dis = INF; dfs(1,1,0); if (dis == INF) printf("-1\n"); else printf("%d\n",dis); } return 0; }