hdu 1175 连连看问题

悠悠 2022-08-09 17:43 179阅读 0赞

/** 连连看 Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 25619 Accepted Submission(s): 6356 Problem Description “连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。 如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么 这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过 去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。 玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这 个后台程序。 Input 输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。在接下 来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的 一行是一个正整数q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问 第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。 注意：询问之间无先后关系，都是针对当前状态的！ Output 每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。 Sample Input 3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0 Sample Output YES NO NO NO NO YES Author lwg Recommend We have carefully selected several similar problems for you: 1180 1072 1016 1026 1010 */
    
    /** 要点： 1.两棋子可以消去的条件：是两枚棋子（不能是1枚）；两棋子必须相同且不能为空（0）；两棋子连线上不能有其他 棋子，只能为空；路线转折次数不能超过两次 2.使用广搜来解，但由于广搜搜到的是最短路径，而这道题要求的路线转折次数不超过两次，所以需要的一个标记数组 Min是用来存储数组中能到达各点的最小转折次数的，需要出示化为一个足够大的值 3.正整数n,m(0<n<=1000,0<m<1000),数组的输入从(1,1)开始，一开始没注意，上手就写，然后就一直WA 4.当走到某一点(x,y)时，如果在该点的转折次数不大于Min[x][y],就应当刷新，然后按这条路走下去 5.以前广搜的标记数组只有0,1两种状态，但这儿用于比较，数组的值是用于比较的 思路：一般的bfs是用来求取最短距离的，于是定好起始点，按照四个方向搜索就可以了，每个点只是也只是允许访问 一次，但是在这个连连看当中，是可以允许重复访问点的，因为我们要的不是距离最短的点，而是转弯最少的线路， 于是我们增加了一个变量用于存储转弯的次数，当这个点的转弯的次数变得更少的时候我们就更新这个点到队列当中 去，并更新这个点的turn。于是会走很多冤枉路，耗时很长 */
    
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
    const int S = 1010;
    int n,m;
    int q,sx,sy,dx,dy;
    int grid[S][S],Min[S][S];
    const int dirx[4]={-1,1,0,0},diry[4]={
       0,0,-1,1};
    
    typedef struct {
        int x,y,dir,turn;
    }point;
    
    queue<point>que;
    
    //看P能不能走
    inline bool check(point &P){
        if(P.x>=1&&P.x<=n&&P.y>=1&&P.y<=m) return true;
        return false;
    }
    
    bool bfs(){
        point cur,next;
        while(que.size()){
            cur = que.front();
            //cout<<"x:"<<cur.x<<" y:"<<cur.y<<" dir:"<<cur.dir<<" turn:"<<cur.turn<<endl;
            que.pop();
            if(cur.x==dx&&cur.y==dy&&cur.turn<=2) return true;
            for(int i=0;i<4;i++){
                //当前朝向与下一点的朝向不一样，转向
                if(cur.dir!=i){
                    next.dir=i;
                    next.turn=cur.turn+1;
                }
                else{
                    next.dir=cur.dir;
                    next.turn=cur.turn;
                }
                if(next.turn>2) continue;//一定不符合，剪枝
                next.x=cur.x+dirx[i],next.y=cur.y+diry[i];
                /*Min[next.x][next.y]>=next.turn,尤其要注意这个地方是">="而不能是">"*/
                if(check(next)&&(!grid[next.x][next.y]||(next.x==dx&&next.y==dy))&&Min[next.x][next.y]>=next.turn){
                    que.push(next);
                    Min[next.x][next.y]=next.turn;
                }
            }
        }
        return false;
    }
    
    int main(){
        while(scanf("%d %d",&n,&m)&&(n||m)){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++) scanf("%d",&grid[i][j]);
            }
            //输入测试成功！！
            //Print();
            scanf("%d",&q);
            while(q--){
                scanf("%d %d %d %d",&sx,&sy,&dx,&dy);
                //cout << sx << sy << dx << dy << endl;
                //初始筛选
                if((grid[sx][sy]!=grid[dx][dy])||!grid[sx][sy]||!grid[dx][dy]||(sx==dx&&sy==dy)){
                    printf("NO\n");
                    continue;
                }
                while(que.size()) que.pop();
                memset(Min,1,sizeof(Min));
                point start;
                start.x=sx,start.y=sy,start.turn=0;
                //反正是求能否搜索到目标点，先把四种方向导入进队列中去，不然处理很麻烦
                for(int i=0;i<4;i++){
                    start.dir=i;
                    que.push(start);
                }
                Min[sx][sy]=0;
                if(bfs()) printf("YES\n");
                else printf("NO\n");
            }
        }
        return 0;
    }