首页 > 代码库 > bfs
bfs
找朋友
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%lld & %lluDescription
X,作为户外运动的忠实爱好者,总是不想呆在家里。现在,他想把死宅Y从家里拉出来。问从X的家到Y的家的最短时间是多少。
Input
多组输入。每组测试数据首先输入两个整数n,m(1<= n ,m<=15 )表示地图大小。接下来的n 行,每行n个字符。保证输入数据合法。
Output
若X可以到达Y的家,输出最少时间,否则输出 -1。
Sample Input
3 3X#Y***#*#3 3X#Y*#*#*#
Sample Output
4-1
代码如下:
#include <stdio.h>
#include <string.h>
struct N
{
int x; int y;
int cnt;
}s[500], e, f;
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
char map[16][16];
int vt[16][16];
void bfs(int x, int y, int n, int m)
{
int i;
int j=0; int k=0;
e.x = x;
e.y = y;
e.cnt =0;
s[k++] = e;
vt[e.x][e.y]=1;
while(j < k)
{
e = s[j++] ;
if(map[e.x][e.y]==‘Y‘ )
{
printf("%d\n", e.cnt );
return ;
}
for(i=0; i<4; i++)
{
f.x = e.x + dx[i] ;
f.y = e.y + dy[i] ;
if( 0<=f.x && f.x<n && 0<=f.y && f.y<m && vt[f.x ][f.y]==0 && map[f.x][f.y]!=‘#‘ )
{
f.cnt = e.cnt + 1;
s[k++] = f;
vt[f.x][f.y] = 1;
}
}
}
printf("-1\n");
}
int main()
{
int n, m;
int i, j;
int ff;
while(scanf("%d %d", &n, &m)!=EOF )
{
memset(vt, 0, sizeof(vt));
for(i=0; i<n; i++)
{
scanf("%*c%s", map[i] );
}
//找到起点
ff = 0;
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(map[i][j]==‘X‘)
{
ff=1;
break;
}
}
if(j!=m)
break;
//if(ff=1)
// break;
}
bfs(i, j, n, m );
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。