首页 > 代码库 > hdu 1175 连连看 （深搜）

hdu 1175 连连看 （深搜）

2024-07-16 19:54:38   226人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1175

题目大意：如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子）这样的两个棋子可以消掉。还有一个要注意的地方的就是转弯。转弯的次数不超过两次，这两个棋子才可以在棋盘上消去~

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int sx,sy,bx,by,wan,dir[4][2]= {0,1,0,-1,1,0,-1,0},n,m; 6 int vis[1110][1110],a[1110][1110],flag; 7  8 void dfs(int x,int y,int wan,int fang) 9 {10     if (flag==1)11     return ;12     if (wan==2&&x!=bx&&y!=by)13         return ;14     if (wan>2)15         return ;16     for (int i=0; i<4; i++)17     {18         int X=x+dir[i][0];19         int Y=y+dir[i][1];20         if (X==bx&&Y==by)21             //printf ("Yes\n");22         {23             flag=1;24             return ;25         }26         if (X>0&&X<=n&&Y>0&&Y<=m&&!vis[X][Y]&&a[X][Y]==0)27         {28             vis[X][Y]=1;29             if (fang!=i)30                 dfs(X,Y,wan+1,i);31             else32                 dfs(X,Y,wan,i);33             vis[X][Y]=0;34         }35 36     }37 }38 39 int main ()40 {41     while (~scanf("%d%d",&n,&m))42     {43         if (n==0&&m==0)44             break;45         for (int i=1; i<=n; i++)46             for (int j=1; j<=m; j++)47                 cin>>a[i][j];48         int k;49         cin>>k;50         while (k--)51         {52             flag=0;53             memset(vis,0,sizeof(vis));54             cin>>sx>>sy>>bx>>by;55             if (a[sx][sy]!=a[bx][by]||(a[sx][sy]==0||a[bx][by]==0))56                 printf ("NO\n");57             else58             {59                 dfs(sx,sy,-1,-1);60                 if (flag==1)61                     printf ("YES\n");62                 else63                     printf ("NO\n");64             }65         }66     }67     return 0;68 }

 


联系
我们