湖南科技大学 BFS优先队列之马走日

问题 C: BFS_跳马问题

时间限制: 1 Sec内存限制: 128 MB
提交: 15解决: 12
[提交][状态][讨论版]

题目描述

现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）

输入

第一行输入n表示有n组测试数据
每组测试数据第一行输入2个整数p,q表示棋盘的大小(1<=p,q<=100)
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置
第三行输入m表示图中有多少障碍
接着跟着m行，表示障碍的坐标

输出

马从起点走到终点所需的最小步数
如果马走不到终点输入“can not reach!”

样例输入

2

9 10

1 1 2 3

0

9 10

1 1 2 3

8

1 2

2 2

3 3

3 4

1 4

3 2

2 4

1 3

样例输出

1

can not reach!

提示

此题可选择DFS，也可选择BFS，建议选择BFS(广搜)。一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。

上面的代码是AC 的 但是老师加强了数据后就RE了 现在用优先队列 居然WA26边啊 我哭死啊 当知道我为什么错的瞬间我想砸板凳啊

貌似老师数据有问题

下面为加强数据后AC代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
int step[10][2]={0,0,0,0,2,-1,2,1,1,2,-1,2,-2,-1,-2,1,1,-2,-1,-2},n,m;
int p[5][2]={0,0,1,0,0,1,-1,0,0,-1};
int map[200][200],e_x,e_y,flag,mm,s_x,s_y;
struct haha
{
int x;
int y;
int step;
friend bool operator <(haha a,haha b)
{
return a.step>b.step;
}

}q,temp;
void BFS()
{
int i,x,y,x1,y1;
priority_queue<haha>que;
q.x=s_x;q.y=s_y;q.step=0;
map[s_x][s_y]=1;
que.push(q);
while(!que.empty())
{
temp=que.top();
que.pop();
if(temp.x==e_x&&temp.y==e_y)
{
mm=temp.step; return;
}
for(i=2;i<10;i++)
{
x=temp.x+step[i][0];
y=temp.y+step[i][1];
x1=temp.x+p[i/2][0];
y1=temp.y+p[i/2][1];
if(map[x1][y1]==2) continue;
if(x>=1&&x<=n&&y>=1&&y<=m&&!map[x][y])
{
map[x][y]=1;
q.x=x; q.y=y; q.step=temp.step+1;
que.push(q);
}

}

}
}
int main()
{
int cas,i,k,x,y;
scanf("%d",&cas);
while(cas--)
{
scanf("%d %d",&n,&m);//n是控制后面 m是控制前面
scanf("%d %d %d %d",&s_x,&s_y,&e_x,&e_y);
scanf("%d",&k);
memset(map,0,sizeof(map));
while(k--)
{
scanf("%d %d",&x,&y);
map[x][y]=2;

}
mm=999999999;
flag=0;
// if(map[e_x][e_y]!=2) //只去掉了这句话就对了 难道终点也可以是障碍物的位置???? 数据有问题 饿感觉
BFS();
if(mm!=999999999) printf("%d\n",mm);
else printf("can not reach!\n");
}
return 0;
}