学步园

HDU1175题目描述

BFS

#include<stdio.h>
#include<queue>
#include<memory>
using namespace std;

int map[1010][1010];
int n,m;
int ex,ey;
//搜索方向
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int flag[1010][1010];

struct point{
    int x;
    int y;
    int step;//转弯的次数
    int flag;//搜索的方向四个方向分别用 0,1,2,3表示
};


int Search(int sx,int sy){
    queue<point> Q;
    point t1,t2;
    t1.x=sx;
    t1.y=sy;
    t1.step=0;
    t1.flag=-1;
    Q.push(t1);
    while(!Q.empty()){
        t1=Q.front();
        Q.pop();
	//能够相连返回1
        if(t1.x==ex&&t1.y==ey&&t1.step<=3){
            return 1;
        }
    
        for(int i=0;i<4;i++){
            int dx=t1.x+dir[i][0];
            int dy=t1.y+dir[i][1];
            if(dx>0&&dy>0&&dx<=n&&dy<=m&&map[dx][dy]==0){//数组下标是否越界，并且该点能否通过。
                if(t1.step<=3){//转弯次数小于等于3的才有可能进入队列
                    t2.flag=i;
                    t2.x=dx;
                    t2.y=dy;
                    if(t2.flag==t1.flag){//当前点的方向与父点方向相同
                        t2.step=t1.step;
                    }
                    else t2.step=t1.step+1;//方向不同
                    if(flag[t2.x][t2.y]>=t2.step&&t2.step<=3){//如果到达该点时转弯的次数比前面已到达该点时的转弯次数大，就不需要入队。
                        flag[t2.x][t2.y]=t2.step;
                        Q.push(t2);
                    }
                }
            }
        }
    }
    return 0;
}

int main(){
    int i,j,test;
    int sx,sy;
    while(scanf("%d%d",&n,&m),n){
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d",&map[i][j]);
            }
        }
        scanf("%d",&test);
        while(test--){
            memset(flag,4,sizeof(flag));
            scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
            if(map[sx][sy]&&map[ex][ey]&&map[sx][sy]==map[ex][ey]){
                int t=map[ex][ey];
                map[ex][ey]=0;
                if(Search(sx,sy)){
                    
                    printf("YES\n");
                }
                else{
                    printf("NO\n");
                }
                map[ex][ey]=t;
            }
            else{
                printf("NO\n");
            }
        }
    }
    return 0;
}