首页 > 代码库 > HDU1175:连连看 [DFS]

HDU1175:连连看 [DFS]

2024-08-28 00:33:46   218人阅读

题目链接：连连看

 

题意：

给出一张n*m的图，有q次询问，每次询问给出两个位置，问这两个位置是否能够相消

相消的条件：

1.两个位置可以用线相连且弯折度不超过2

2.两位置数字相同且不为0

 

分析：

用一个二维数组存储该位置的弯折度，注意剪枝顺序，详情见代码

一开始写dx[],dy[]的时候写成一维，却wa，不清楚为什么

 

技术分享
 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5  6 int n,m,a[1010][1010],dx[5]={0,0,-1,0,1},dy[5]={0,1,0,-1,0},q,x1,y1,x2,y2,cnt,fang[1010][1010],flag; 7  8 void dfs(int x,int y,int cnt,int f) 9 {10     //注意剪枝的顺序11     if(flag) return ;//若已有结果，则直接返回12     if(x<1||y<1||x>n||y>m||cnt>2) return ;13     if((x==x2)&&(y==y2)) {flag=1;return ;}14     if(a[x][y]) return ;15     //若该点已有弯折度且当前局面到x,y的弯折度大于其他局面的弯折度，则返回16     if((fang[x][y]!=-1)&&(cnt>=fang[x][y])) return ;17     fang[x][y]=cnt;18     for(int i=1;i<=4;++i)19     {20         int xx=x+dx[i],yy=y+dy[i];21         if(f!=i) dfs(xx,yy,cnt+1,i);else dfs(xx,yy,cnt,i);22     }23 }24 25 int main()26 {27     while(scanf("%d%d",&n,&m)!=EOF)28     {29         if(n==0&&m==0) return 0;30         for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) {scanf("%d",&a[i][j]);}31         for(scanf("%d",&q);q--;)32         {33             memset(fang,-1,sizeof(fang));34             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);35             flag=0;36             if(a[x1][y1]!=a[x2][y2]||a[x1][y1]==0) {puts("NO");continue;}37             fang[x1][y1]=0;38             for(int i=1;i<=4;++i) dfs(x1+dx[i],y1+dy[i],0,i);39             if(flag) puts("YES");else puts("NO");40         }41     }42 }
View Code

 

HDU1175:连连看 [DFS]


联系
我们