首页 > 代码库 > HDU-1175-连连看

HDU-1175-连连看

2024-07-26 10:10:53   224人阅读

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1175

 

普通的bfs，外加判断转角次数，就ko了。

#include<iostream>

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
 
struct node
{
    int x,y;
    int t,d;
};
 
int n,m,map[1002][1002],prove;
int visit[1002][1002];
int qry,sx,sy,ex,ey;
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
 
queue<node> q;
 
void bfs()
{
    while(!q.empty())
    q.pop();
    memset(visit,0,sizeof(visit));
    node s,e;
    s.x=sx;   s.y=sy;
    s.t=0;    s.d=-1;
    q.push(s);
    while(q.size())
    {
        s=q.front();
        q.pop();
        if(s.t>2)
        continue;
        if(s.x==ex&&s.y==ey)
        {
            prove=1;
            printf("YES\n");
            break;
        }
        for(int i=0;i<4;i++)
        {
            e.x=s.x+dx[i];    e.y=s.y+dy[i];
            if(e.x<1||e.x>n||e.y<1||e.y>m||visit[e.x][e.y])
            continue;
            if(map[e.x][e.y]==0||(e.x==ex&&e.y==ey))
            {
                if(s.d==-1||s.d==i)
                {
                    e.d=i;
                    e.t=s.t;
                    q.push(e);
                    visit[e.x][e.y]=1;
                }
                else
                {
                    e.d=i;
                    e.t=s.t+1;
                    q.push(e);
                    visit[e.x][e.y]=1;
                }
            }
        }
    }
}
 
int main(void)
{
    while(scanf("%d%d",&n,&m)==2&&(n+m))
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        scanf("%d",&map[i][j]);
        scanf("%d",&qry);
        for(int i=0;i<qry;i++)
        {
            prove=0;
            cin>>sx>>sy>>ex>>ey;
            if(sx==ex&&sy==ey)
            {
                printf("NO\n");
                continue;
            }
            if(map[sx][sy]==map[ex][ey]&&map[sx][sy]!=0)
            bfs();
            if(!prove)
            printf("NO\n");
        }
    }
    return 0;
}

HDU-1175-连连看


联系
我们