现在的位置: 首页 > 综合 > 正文

hdu 1175 连连看

2013年08月07日 ⁄ 综合 ⁄ 共 1223字 ⁄ 字号 评论关闭
/*
    总结:
    dfs题一定要注意剪枝:
    判断是否访问过,是否溢出,是否不符合条件,
        注意当前点与初始点的关系、初始点和结束点的关系
    
*/
#include <iostream>
#include <cstdio>
#define maxn 1005
using namespace std;
int m,n,q;
int x1,y1,x2,y2;
int wan;
int flag;
int map[maxn][maxn];
int visit[maxn][maxn];
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void dfs(int x,int y,int wan,int d)
{
    /*判断条件*/
    if(x==x2 && y==y2 )  {/*printf("a:%d b:%d\n");*/flag=1;}
    if(flag)    return;
    if(wan>2)   return;
    if(wan==2 && x2!=x && y2!=y)    return;
    //判断条件
    
    //if(wan>2 || x>n || x<1 || y>m || y<1) {printf("sfa\n");  return;}
    for(int i=0;i<4;i++)
    {
        int a=x+dir[i][0],b=y+dir[i][1];
        //printf("%d %d\n",a,b);
        if(a==x2 && b==y2)  {flag=1;break;}
        if(visit[a][b])	continue;
        if(map[a][b]==0  &&  a<=n && a>0 && b<=m && b>0)
        {
           // printf("a:%d b:%d==0\n",a,b);
           // if(a!=ex && b!=ey)  wan++;
           if(d!=-1 && i!=d)  wan++;
            visit[a][b]=1;
            dfs(a,b,wan,i);
            visit[a][b]=0;
            if(d!=-1 && d!=i)
                wan--;
            //if(a==ex && b==ey)  wan--;
        }
    }

}
int main()
{
    while(scanf("%d%d",&n,&m),m||n)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                visit[i][j]=0;
            }

        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(map[x1][y1]!=map[x2][y2] || map[x1][y1]==0)
            {
                printf("NO\n");
                continue;
            }
            if(x1==x2 && y1==y2)
			{
                printf("NO\n");
                continue;
            }
            wan=0;
            //ex=x1,ey=y1;
            flag=0;
            visit[x1][y1]=1;
            dfs(x1,y1,0,-1);
            visit[x1][y1]=0;
            if(flag)
                printf("YES\n");
            else
                printf("NO\n");
        }

    }
}

抱歉!评论已关闭.