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 電影節