好贷网好贷款

HDU 1175 连连看

发布时间:2016-12-5 18:31:35 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 1175 连连看",主要涉及到HDU 1175 连连看方面的内容,对于HDU 1175 连连看感兴趣的同学可以参考一下。

转载请注明出处:http://blog.csdn.net/a1dark 分析:这题有点坑、数据有点问题、做不过的就看看别人过了的代码、就会发现要错误的理解才能AC、 这道题可以DFS或者BFS都能轻松过、但是还是要养成剪枝的习惯、 #include <stdio.h> #include <string.h> int map[1015][1015]; int vis[1015][1015]; int n,m,x1,x2,y1,y2,flag; void dfs(int x,int y,int z,int k){ if(flag) return; if(k>=3) return ; if(x<=0 || y<=0 || x>n || y>m) return ; if(x == x2 && y == y2){ flag = 1; return ; } if(k == 2){ if(!(z == 1&& x>x2&& y==y2||z == 2&&x<x2&&y==y2||z ==3&&y>y2&&x==x2||z==4&&y<y2&&x==x2)) return; } if(map[x][y]!=0) return; if(vis[x][y]) return ; vis[x][y] = 1; if(z == 1){ dfs(x-1,y,1,k); dfs(x+1,y,2,k+1); dfs(x,y-1,3,k+1); dfs(x,y+1,4,k+1); } else if(z == 2){ dfs(x-1,y,1,k+1); dfs(x+1,y,2,k); dfs(x,y-1,3,k+1); dfs(x,y+1,4,k+1); } else if(z == 3){ dfs(x-1,y,1,k+1); dfs(x+1,y,2,k+1); dfs(x,y-1,3,k); dfs(x,y+1,4,k+1); } else if(z == 4){ dfs(x-1,y,1,k+1); dfs(x+1,y,2,k+1); dfs(x,y-1,3,k+1); dfs(x,y+1,4,k); } vis[x][y] = 0; } int main(){ while(~scanf("%d%d",&n,&m)){ if(!n&&!m) break; int i,j; for(i = 1; i<=n; i++) for(j = 1; j<=m; j++) scanf("%d",&map[i][j]); int t; scanf("%d",&t); while(t--){ flag = 0; memset(vis,0,sizeof(vis)); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x1 == x2 && y1 == y2 && map[x1][y1]!=0) printf("NO\n"); else if(map[x1][y1] == map[x2][y2] && map[x1][y1]){ dfs(x1-1,y1,1,0); dfs(x1+1,y1,2,0); dfs(x1,y1-1,3,0); dfs(x1,y1+1,4,0); if(flag) printf("YES\n"); else printf("NO\n"); } else printf("NO\n"); } } return 0; }

上一篇:struts2框架中,使用iframe/form方式的ajaxupload,提示下载json的问题解决
下一篇:问题3:如何用递归算法判断一个数组是否是递增?

相关文章

关键词: HDU 1175 连连看

相关评论