当然选择原谅她呀
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) Total Submission(s) : 64 Accepted Submission(s) : 22 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem 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 Author wanglang
代码 BFS AC代码
#include<string.h> #include<stdio.h> #include<queue> using namespace std; /************************************/ struct Node{ int x; int y; int step; }; int to[4][2]={1,0,-1,0,0,1,0,-1}; bool mp[23][23]; int n,m; void getmap() { int a; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&a); mp[i][j]=!a; } } } queue<Node>Q; void bfs() { Node e={1,1,0};int flag=0; Node now,nexts; while(!Q.empty()) Q.pop(); Q.push(e); while(!Q.empty()) { now=Q.front();Q.pop(); if(now.x==n&&now.y==m) { flag=1;break;} for(int i=0;i<4;i++) { nexts.x=now.x+to[i][0]; nexts.y=now.y+to[i][1]; nexts.step=now.step+1; if(mp[nexts.x][nexts.y]) mp[nexts.x][nexts.y]=0,Q.push(nexts); } } printf("%d\n",flag?now.step:-1); } int main() { while(~scanf("%d%d",&n,&m)) { memset(mp,0,sizeof(mp)); getmap(); bfs(); } return 0; }dfs AC代码
#include<string.h> #include<stdio.h> #include<queue> using namespace std; /************************************/ const int inf =0x3f3f3f3f; int step; int to[4][2]={1,0,-1,0,0,1,0,-1}; bool mp[23][23]; int n,m; void getmap() { int a; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&a); mp[i][j]=!a; } } } void dfs(int x,int y,int ge) { mp[x][y]=0; if(x==n&&y==m) {step=min(step,ge);return;} int xx,yy; for(int i=0;i<4;i++) { xx=x+to[i][0]; yy=y+to[i][1]; if(mp[xx][yy]) { dfs(xx,yy,ge+1); mp[xx][yy]=1;// 回溯下要 } } } int main() { while(~scanf("%d%d",&n,&m)) { memset(mp,0,sizeof(mp)); getmap(); step=inf; dfs(1,1,0); if(step==inf) printf("-1\n"); else printf("%d\n",step); } return 0; }