随笔-68  评论-10  文章-0  trackbacks-0

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 阅读(1940) 评论(1)  编辑 收藏 引用 所属分类: 搜索

评论:
# re: hdu1175 2011-05-27 15:11 | TmacKiller
双向的就行了,楼主可以试一下  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理