找朋友
Time Limit: 1000MS
Memory Limit: 65536KB
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 3 X#Y *#* #*#
Example Output
4 -1
Hint
Author
zmx
#include <stdio.h>
#include <string.h>
struct node
{int x;int y;int z;
} link[404], ans;
char mp[20][20];
int visit[20][20];
int tp, op, tn, tm, x1, x2, y1, y2;
int jn[] = { 0, 0, -1, 1};
int jm[] = { 1, -1, 0, 0};
int BFS(int n, int m)
{link[tp].x = x1, link[tp].y = y1, link[tp].z = 0;visit[link[tp].x][link[tp].y] = 1;tp++;while(op < tp){ans = link[op++];if(mp[ans.x][ans.y] == 'Y'){return ans.z;}for(int i = 0; i < 4; i++){tn = ans.x + jn[i];tm = ans.y + jm[i];if(tn >= 0 && tn < n && tm >= 0 && tm < m){if(mp[tn][tm] != '#' && visit[tn][tm] == 0){link[tp].x = tn, link[tp].y = tm, link[tp].z = ans.z + 1;tp++;visit[tn][tm] = 1;}}}}return -1;
}
int main()
{int n, m, i, j;while(scanf("%d %d", &n, &m) != EOF){//getchar();tp = op = 0;memset(visit, 0, sizeof(visit));for(i = 0; i < n; i++){scanf("%s", mp[i]);}for(i = 0; i < n; i++){for(j = 0; j < m; j++){if(mp[i][j] == 'X'){x1 = i, y1 = j;break;}}if(j != m)break;}printf("%d\n", BFS(n, m));}return 0;
}