sdut 2779 找朋友(dfs)

2019-11-08 01:38:44

字体：大中小

来源：转载

供稿：网友

PRoblem Description X，作为户外运动的忠实爱好者，总是不想呆在家里。现在，他想把死宅Y从家里拉出来。问从X的家到Y的家的最短时间是多少。为了简化问题，我们把地图抽象为n*m的矩阵，行编号从上到下为1 到 n，列编号从左到右为1 到 m。矩阵中’X’表示X所在的初始坐标，’Y’表示Y的位置 , ’#’表示当前位置不能走，’ * ’表示当前位置可以通行。X每次只能向上下左右的相邻的 ’*’ 移动，每移动一次耗时1秒。 Input 多组输入。每组测试数据首先输入两个整数n，m(1<= n ,m<=15 )表示地图大小。接下来的n 行，每行m个字符。保证输入数据合法。 Output 若X可以到达Y的家，输出最少时间，否则输出 -1。 Example Input

3 3 X#Y

#*#3 3X#Y*#*#*#

Example Output

4 -1

#include <cstdio>#include <cstring>#include <iostream>#include <queue>using namespace std;char map[20][20];int book[20][20];int move[4][2]={{0,1}, {0,-1}, {-1,0}, {1,0} };struct node{ int x; int y; int time;}p1,p2;int n,m;void bfs(int x,int y){ p1.x=x; p1.y=y; p1.time=0; queue <node> Q; Q.push(p1); book[x][y]=1; int k; while(!Q.empty()) { p1=Q.front(); Q.pop(); if(map[p1.x][p1.y]=='Y') { printf("%d/n",p1.time ); return ; } for(k=0;k<4;k++) { p2.x=p1.x+move[k][0]; p2.y=p1.y+move[k][1]; if(p2.x>=0&&p2.x<n&&p2.y>=0&&p2.y<m&&!book[p2.x][p2.y]&&map[p2.x][p2.y]!='#') { book[p2.x][p2.y]=1; p2.time=p1.time+1; Q.push(p2); } } } printf("-1/n");}int main(){ int i,j; while(cin>>n>>m) { memset(map,0,sizeof(map)); memset(book,0,sizeof(book)); for(i=0;i<n;i++) { scanf("%s",map[i]); } for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(map[i][j]=='X') break; } if(j<m) break; } bfs(i,j); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 168KBSubmit time: 2017-02-20 20:39:23****************************************************/

上一篇：有向图　　拓扑排序topoLogicalSort

下一篇：SDUT 2797 电影节

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注