#include <iostream>
using namespace std;
struct note{
int x;
int y;
int step;
};
int main()
{
struct note que[2501];
int a[51][51]={0};
int book[51][51]={0};
int next[4][2]={
{0,1},//往右出发
{1,0},//往下出发
{-1,0},//往上出发
{0,-1}//往左出发
};
int head=1,tail=1,m,n,i,j;
int startx,starty,p,q;
cout<<"输入几行几列"<<" ";
cin>>m>>n;
cout<<"请输入m行n列的地图"<<endl;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
cin>>a[i][j];
}
}
cout<<"请输入起始位置"<<" ";
cin>>startx>>starty;
cout<<"请输入终点位置"<<" ";
cin>>p>>q;
//初始化队列
que[tail].x=startx;
que[tail].y=starty;
que[tail].step=0;
tail++;
book[startx][starty]=1;//标记该点在路径中出现
int k,flag=0,tx,ty;//用来标记是否达到目标点,0表示没有到达,1表示已经达到。
while(head<tail){
for(k=0;k<4;k++){
tx=que[tail].x+next[k][0];
ty=que[tail].y+next[k][1];
if(tx<1||tx>m||ty<1||ty>n){
continue;
}
if(book[tx][ty]==0&&a[tx][ty]==0){
book[tx][ty]=1;
que[tail].x=tx;
que[tail].y=ty;
que[tail].step=que[head].step+1;
tail++;
}
if(tx==p&&ty==q){
flag=1;
break;
}
}
if(flag==1){
break;
}
head++;
}
cout<<que[tail-1].step<<endl;
return 0;
}
死循环了。
同为ACMer,广搜建议用队列 / 优先队列实现,下面是我的模板,谢谢!
/*
题意:
有5个整数,表示不同类型的迷宫区:
0--------墙
1--------路
2--------起始位置
3--------迷宫的出口
4--------重置炸弹爆发时间的位置
如果在炸弹爆炸前能逃离迷宫,输出最短时间,否则输出-1;
最一开始看到这道题不知道该怎么下手,不知道是不是该走4,觉得4比较特殊。
首先肯定用广搜,但是一个点可能走两次,可是标记过就不能走了,所以我遇到4时,
就以4为一个新的起点,进行广搜,同时把上次所用的时间加上,标记4,同一个4不能重复走。
但就是因为标记和先后要走的方向,走4的先后顺序不同,路程也就不同。
如果4是必经之路则必须走,如果不是则不用走,利用之前简单地广搜思想就可以,无非是走过的路不再标记,只标记4.
*/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
struct note
{
int x, y, t, s;
note(int a, int b, int c, int d)
{
x = a;
y = b;
t = c;
s = d;
}
};
int st[10][10];
int mk[10][10];
int n, m, ex, ey, f, s;
int nx[4][2] = { 1, 0, 0, 1, 0, -1, -1, 0 };
void bfs(int x, int y)
{
int i;
queue<note> qw;
qw.push(note(x, y, 6, 0));
while (!qw.empty())
{
note q = qw.front();
qw.pop();
for (i = 0; i<4; i++)
{
int tx = q.x + nx[i][0];
int ty = q.y + nx[i][1];
if (tx == ex && ty == ey && q.t - 1>0)
{
f = 1;
s = q.s + 1;
return;
}
if (tx >= 0 && ty >= 0 && tx<n && ty<m && st[tx][ty] != 0 && q.t>1 && !mk[tx][ty])
{
if (st[tx][ty] == 4)
{
mk[tx][ty] = 1;
qw.push(note(tx, ty, 6, q.s + 1));
}
else
qw.push(note(tx, ty, q.t - 1, q.s + 1));
}
}
}
return;
}
int main()
{
int t, i, j, sx, sy;
scanf("%d", &t);
while (t--)
{
memset(mk, 0, sizeof(mk));
scanf("%d%d", &n, &m);
for (i = 0; i<n; i++)
for (j = 0; j<m; j++)
{
scanf("%d", &st[i][j]);
if (st[i][j] == 2)
{
sx = i, sy = j;
mk[i][j] = 1;
}
if (st[i][j] == 3)
ex = i, ey = j;
}
f = 0;
bfs(sx, sy);
if (!f)
printf("-1\n");
else
printf("%d\n", s);
}
return 0;
}