BFS. 题目来源: http://acm.hdu.edu.cn/showproblem.php?pid=1175
由于bfs按层次进行搜所,得到的是从起点到终点的最短路径,但是题目要求我们找一条转向不超过2次的.因此我们可以在此基础上加上一个记录转向次数的数组.对于那些被扩展的点,如果它的转向次数小于等于数组记录的值,那么还可以再次入队列.如下面一组数据:
1 1 1 0 1
1 0 0 0 1
2 0 2 0 1
1 0 1 0 1
1 1 0 0 1
2
5 2 1 5
5 2 1 2
考虑 5 2 1 5这组,如果我们优先扩展上面,则点(2,4)先被标记为1(代表有一次转弯), 然而按此条路径显然不行.但是我们在扩展红色这条路时,可以把(2,4)继续如队列(当前情况扩展时转弯也为1),显然这条路满足条件.
我做这道题时,想到的是按行列扩展,结果队列爆掉了.因为太多重复无用的点进入了队列.
详细见代码:
#include<iostream>
#include<queue>
using namespace std;
const int inf=10000;
int map[1005][1005];
int hash[1005][1005];
int n,m,p;
int x1,y1,x2,y2;
int dir[4][2]=
{-1,0,1,0,0,-1,0,1};
typedef struct node
{
int x,y,times,direc;
node(){}
node(int xx,int yy,int tt,int ff):x(xx),y(yy),times(tt),direc(ff){}
}NODE;
bool bfs()
{
queue<NODE> q;
NODE temp,tt;
q.push(NODE(x1,y1,0,-1));
hash[x1][y1]=0;
while(!q.empty())
{
temp=q.front();
q.pop();
for(int i=0;i<4;i++)
{
tt.x=temp.x+dir[i][0];
tt.y=temp.y+dir[i][1];
if(temp.direc==-1) {tt.direc=i;tt.times=0;}
else if(i==temp.direc) {tt.direc=temp.direc;tt.times=temp.times;}
else {tt.direc=i;tt.times=temp.times+1;}
if(tt.x>=1&&tt.x<=n&&tt.y>=1&&tt.y<=m&&tt.times<=2&&tt.times<=hash[tt.x][tt.y])
{
if(map[tt.x][tt.y]==0||(tt.x==x2&&tt.y==y2))
{
hash[tt.x][tt.y]=tt.times;
if(tt.x==x2&&tt.y==y2)
return true;
q.push(tt);
}
}
}
}
return false;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(m||n))
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&map[i][j]);
scanf("%d",&p);
while(p--)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
hash[i][j]=inf;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(map[x1][y1]!=map[x2][y2]||map[x1][y1]==0||(x1==x2&&y1==y2)) printf("NO\n");
else if(bfs()) printf("YES\n");
else printf("NO\n");
}
}
//system("pause");
return 0;
}
posted on 2010-08-21 11:05
wuxu 阅读(1979)
评论(1) 编辑 收藏 引用 所属分类:
搜索