hdu 1175 连连看

不知道为什么不用flag直接返回bfs的结果会错,被坑了好久。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;

struct node
{
    int x,y,s,d;
} t,t0;

int n,m,mp[1024][1024],vis[1024][1024];
int x,y,x2,y2,flag;
int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};

void bfs()
{
    queue<node>q;
    if(x==x2&&y==y2) return ;
    if(mp[x][y]==0||mp[x2][y2]==0) return ;
    if(mp[x][y]!=mp[x2][y2]) return ;
    memset(vis,5,sizeof(vis));
    t.x=x;
    t.y=y;
    t.s=0;
    t.d=-1;
    q.push(t);
    while(!q.empty())
    {
        t0=q.front();
        //printf("%d %d %d
",t0.x,t0.y,t0.s);
        q.pop();
        if(t0.x==x2&&t0.y==y2&&t0.s<=2) {flag=1;return ;}
        for(int i=0; i<4; i++)
        {
            t=t0;
            t.x+=dx[i];
            t.y+=dy[i];
            if(t.x<1||t.x>n||t.y<1||t.y>m) continue;
            if(mp[t.x][t.y]==0||(t.x==x2&&t.y==y2))
            {
                t.d=i;
                if(i!=t0.d&&-1!=t0.d) t.s++;
                if(t.s>=3) continue;
                if(t.s<vis[t.x][t.y])
                {
                    q.push(t);
                    vis[t.x][t.y]=t.s;
                }
            }
        }
    }
    //return;
}

int main()
{
    while(~scanf(" %d %d",&n,&m))
    {
        if(n==0||m==0) break;
        for(int i=1; i<=n; i++)
         for(int j=1; j<=m; j++)
            scanf("%d",&mp[i][j]);

        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d %d %d %d",&x,&y,&x2,&y2);
            flag=0;
            bfs();
            if(flag) printf("YES
");
            else printf("NO
");
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。http://xiang578.top/

原文地址:https://www.cnblogs.com/xryz/p/4848039.html