DFS解决最短路径问题
程序代码:
#include<stdio.h> #include<string.h> #define MAX 100 int vis[MAX][MAX]={0}, map[MAX][MAX];//其中的1表示墙壁,0表示可以走的路 int min = 10000; int n = 0; void dfs(int depth, int x, int y)//x代表行,y代表列 { if(x >= n || x < 0 || y >= n || y < 0) return; if(vis[x][y] == 1 || map[x][y] == 1) return; if(x == y && y==4) { if(min > depth) min = depth; return; } vis[x][y] == 1; dfs(depth+1,x-1,y); dfs(depth+1,x,y-1); dfs(depth+1,x,y+1); dfs(depth+1,x+1,y); vis[x][y] == 0; } int main() { scanf("%d", &n); memset(map,0,sizeof(map)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { scanf("%d",&map[i][j]); vis[i][j] = map[i][j]; } dfs(0,0,0); if(min == 10000) printf("No\n"); else printf("%d\n",min); return 0; }//不能运行,输出最短步数就行..
烦劳大佬们解答一下,不胜感激!!!!