hdu-1175（bfs+剪枝）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1175

思路：用bfs，注意要转弯的次数，次数大于两次就跳过。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int a[1002][1002],x1,x2,y1,y2,k,n,m,vis[1002][1002];
int zz[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct Node{
    int x,y,num,fx;
}; 
bool bfs()
{
    memset(vis,0,sizeof(vis));
    queue <Node> q;
    Node tp,tmp;
    tp.x=x1;tp.y=y1;
    tp.fx=0;tp.num=0;
    q.push(tp);
    vis[x1][y1]=1;
    while(!q.empty())
    {
        tp=q.front();
        q.pop();
        //cout<<tp.x<<" "<<tp.y<<endl;
        if(tp.x==x2&&tp.y==y2&&tp.num<=2) return true;
        for(int i=0;i<4;i++)
        {
            tmp.x=tp.x+zz[i][0];
            tmp.y=tp.y+zz[i][1];
            if(tp.fx==0)
            {
                tmp.fx=i+1;tmp.num=tp.num;
            }
            else
            {
                if(tp.fx==i+1) tmp.fx=i+1,tmp.num=tp.num;
                else tmp.fx=i+1,tmp.num=tp.num+1;
            }
            if(tmp.num>2) continue;
            if(tmp.x<=0||tmp.x>n||tmp.y<=0||tmp.y>m) continue;
            if(vis[tmp.x][tmp.y]==1) continue;
            if(a[tmp.x][tmp.y]==0||tmp.x==x2&&tmp.y==y2)
            {
                vis[tmp.x][tmp.y]=1;
                q.push(tmp);
            }
        }
    }
    return false;
}
int main(void)
{
    int i,j;
    while(cin>>n>>m&&(n+m))
    {
        for(i=1;i<=n;i++)
           for(j=1;j<=m;j++) cin>>a[i][j];
        cin>>k;
        while(k--)
        {
            cin>>x1>>y1>>x2>>y2;
            if(a[x1][y1]!=a[x2][y2]||(a[x1][y1]==a[x2][y2]&&a[x1][y1]==0)||(a[x1][y1]==a[x2][y2]&&x1==y1&&x2==y2))
            {
                cout<<"NO"<<endl;
                continue;
            }
            if(bfs()==true) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}