#2
康明贤2018-11-23 11:31
#include<iostream>
#include<queue> using namespace std; void bfs(); int x1,y1,x2,y2; int used[50][50]={0} ; int s[20][20]={0}; char route[20][20]={0}; queue <int> x; queue <int> y; //在这里需要考虑一个二维的情况,故需要给x,y各一个队列 int main() { int i,j; cin>>x1>>y1>>x2>>y2; x.push(x1); y.push(y1); //相当于识别起始位置 for(i=1;i<=12 ;i++) { for(j=1;j<=12;j++) { cin>>route[i][j]; } } bfs(); return 0; } void bfs() { int i,j,flag=1; while(flag == 1) { if(s[x2][y2] != 0) //在没走到终点之前,终点位置的数值始终为0 //一旦发现不是0了,说明计数已经“计到了”这个位置。当前数值也就代表了步数 //因为采取了广搜,所以不必担心,首先到达终点的情况肯定是“最小步数”的情况 { cout<<s[x2][y2]<<endl; break; } x1=x.front(); y1=y.front(); //(x1,y1)始终为当前所在的位置 x.pop(); y.pop(); used[x1][y1]=1; //走过的不能重复走了!!!!! 之前忘了这个,结果走了很多重复的路!!!!!!!!!!! if(route[x1-1][y1] == '.'&&used[x1-1][y1]==0) //向上走得通 { x.push(x1-1); y.push(y1); s[x1-1][y1]=s[x1][y1]+1; } if(route[x1+1][y1] == '.'&&used[x1+1][y1]==0) //向下走得通 { x.push(x1+1); y.push(y1); s[x1+1][y1]=s[x1][y1]+1; } if(route[x1][y1-1] == '.'&&used[x1][y1-1]==0) //向左走得通 { x.push(x1); y.push(y1-1); s[x1][y1-1]=s[x1][y1]+1; } if(route[x1][y1+1] == '.'&&used[x1][y1+1]==0) //向右走得通 { x.push(x1); y.push(y1+1); s[x1][y1+1]=s[x1][y1]+1; } } } |
时限:1000ms 内存限制:10000K 总时限:3000ms
描述
有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫,黑色部分表示建筑物,白色部分是路。电子老鼠可以在路上向上、下、左、右行走,每一步走一个格子。现给定一个起点S和一个终点T,求出电子老鼠最少要几步从起点走到终点。
输入
本题包含一个测例。在测例的第一行有四个由空格分隔的整数,分别表示起点的坐标S(x.y)和终点的坐标T(x,y)。从第二行开始的12行中,每行有12个字符,描述迷宫的情况,其中'X'表示建筑物,'.'表示路.
输出
输出一个整数,即电子老鼠走出迷宫至少需要的步数。
输入样例
2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX
输出样例
28
程序代码:
#include <stdio.h>
#include <string.h>
struct note
{
int x;//横坐标
int y;//纵坐标
int s;//步数
};
int main()
{
struct note que[145];
int book[13][13] = {0};
char a[13][13];
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int head,tail;
int i,k,n=12,m=12,startx,starty,p,q,tx,ty,flag;
scanf("%d %d %d %d",&startx,&starty,&p,&q);
getchar();
for(i=1;i<=n;i++)
gets(a[i]);
//队列初始化
head = 1;
tail = 1;
//往队列插入迷宫入口坐标
que[tail].x = startx;
que[tail].y = starty;
que[tail].s = 0;
tail++;
book[startx][starty] = 1;
flag = 0;//用来标记是否到达目标点,0表示暂未,1表示到达
//当队列不为空时循环
while(head<tail)
{
//枚举四个方向
for (k=0;k<=3;k++)
{
//计算下一个点的坐标
tx = que[head].x+next[k][0];
ty = que[head].y+next[k][1];
//判断是否越界
if (tx<1||tx>n||ty<1||ty>m)
{
continue;
}
if(a[tx][ty]=='.'&&book[tx][ty]==0)
{
book[tx][ty] = 1;
que[tail].x = tx;
que[tail].y = ty;
que[tail].s = que[head].s+1;
tail++;
}
if (tx==p&&ty==q)
{
flag = 1;
break;
}
}
if (flag == 1)
{
break;
}
head++;
}
printf("%d\n",que[tail-1].s);
return 0;
}
/*
6 6 11 11
XXXXXXXXXXXX
X..........X
X.XXXXXXXX.X
X.X......X.X
X.X.XXXX.X.X
X.X.X..X.X.X
X.X.XX.X.X.X
X.X.XX.X.X.X
X.X....X.X.X
X.XXXXXX.X.X
X........X.X
XXXXXXXXXXXX
58
*/
/*
11 11 4 4
XXXXXXXXXXXX
X........XXX
X.XXXXXX...X
X...XX.XXX.X
X.XXXX.....X
X.X..X..X.XX
X.X....XX.XX
X...XX..X.XX
X..XXXX.X.XX
X.XXXX.....X
X..X...XXX.X
XXXXXXXXXXXX
20
*/[code]
[/code]#include <string.h>
struct note
{
int x;//横坐标
int y;//纵坐标
int s;//步数
};
int main()
{
struct note que[145];
int book[13][13] = {0};
char a[13][13];
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int head,tail;
int i,k,n=12,m=12,startx,starty,p,q,tx,ty,flag;
scanf("%d %d %d %d",&startx,&starty,&p,&q);
getchar();
for(i=1;i<=n;i++)
gets(a[i]);
//队列初始化
head = 1;
tail = 1;
//往队列插入迷宫入口坐标
que[tail].x = startx;
que[tail].y = starty;
que[tail].s = 0;
tail++;
book[startx][starty] = 1;
flag = 0;//用来标记是否到达目标点,0表示暂未,1表示到达
//当队列不为空时循环
while(head<tail)
{
//枚举四个方向
for (k=0;k<=3;k++)
{
//计算下一个点的坐标
tx = que[head].x+next[k][0];
ty = que[head].y+next[k][1];
//判断是否越界
if (tx<1||tx>n||ty<1||ty>m)
{
continue;
}
if(a[tx][ty]=='.'&&book[tx][ty]==0)
{
book[tx][ty] = 1;
que[tail].x = tx;
que[tail].y = ty;
que[tail].s = que[head].s+1;
tail++;
}
if (tx==p&&ty==q)
{
flag = 1;
break;
}
}
if (flag == 1)
{
break;
}
head++;
}
printf("%d\n",que[tail-1].s);
return 0;
}
/*
6 6 11 11
XXXXXXXXXXXX
X..........X
X.XXXXXXXX.X
X.X......X.X
X.X.XXXX.X.X
X.X.X..X.X.X
X.X.XX.X.X.X
X.X.XX.X.X.X
X.X....X.X.X
X.XXXXXX.X.X
X........X.X
XXXXXXXXXXXX
58
*/
/*
11 11 4 4
XXXXXXXXXXXX
X........XXX
X.XXXXXX...X
X...XX.XXX.X
X.XXXX.....X
X.X..X..X.XX
X.X....XX.XX
X...XX..X.XX
X..XXXX.X.XX
X.XXXX.....X
X..X...XXX.X
XXXXXXXXXXXX
20
*/[code]
最后两个测例,WA!!!