hdu1175 连连看（DFS+剪枝）

hdu1175 连连看（DFS+剪枝）

连连看

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 25111    Accepted Submission(s): 6211

Problem Description

Input

输入数据有多组。每组数据的第一行有两个正整数n,m(0

Output

每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。

Sample Input

3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0

Sample Output

YES NO NO NO NO YES

Author

lwg

Recommend

We have carefully selected several similar problems for you:   ​​1180​​​  ​​​1072​​​  ​​​1026​​​  ​​​1240​​​  ​​​1253​​

​​Statistic​​ |

​​Submit​​ |

​​Discuss​​ |

​​Note​​

前几天做这道题的时候主要是没理解题意。。wa了许多次。我以为拐弯是走在两个数的缝隙里。。。。

气人啊。。

今天才发现是走在数字上。而且只能走0.。也就是只能走在没有棋子的地方。

8642ms险过。。

#include #include int flag,st1,st2,ed1,ed2,m,n;int dir[4][2]={1,0,-1,0,0,1,0,-1},map[1005][1005],vis[1005][1005];bool no(int x,int y){ if(x<0||y<0||x==m||y==n) return true; else return false;}void dfs(int x,int y,int cor,int cnt){ if(cnt>2||flag||x<0||x==m||y<0||y==n) return ; if(x==ed1&&y==ed2) { flag=1; return ; } if(map[x][y]!=0&&cor!=-1) return ; for(int i=0;i<4;i++) { int temp_x=x+dir[i][0]; int temp_y=y+dir[i][1]; if(vis[temp_x][temp_y]||no(temp_x,temp_y)) continue; vis[temp_x][temp_y]=1; if(cor!=i&&cor!=-1) cnt++; dfs(temp_x,temp_y,i,cnt); if(cor!=i&&cor!=-1) cnt--; vis[temp_x][temp_y]=0; }}int main(){ while(scanf("%d %d",&m,&n)!=EOF) { if(m==0&&n==0) break; for(int i=0;i=m||ed1>=m||st2>=n||ed2>=n) { printf("NO\n"); continue; } if(map[st1][st2]!=map[ed1][ed2]||!map[st1][st2]||!map[ed1][ed2]) { printf("NO\n"); continue; } memset(vis,0,sizeof(vis)); flag=0; vis[st1][st2]=1; dfs(st1,st2,-1,0); if(flag) printf("YES\n"); else printf("NO\n"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。