首页 > 代码库 > HDU_1175_dfs
HDU_1175_dfs
http://acm.hdu.edu.cn/showproblem.php?pid=1175
dfs(x,y,i,num),xy表示位置,i表示方向,num表示转向次数,num=2时候的剪枝很重要。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[1005][1005],vis[1005][1005],n,m,endx,endy,dis[4][2] = {{-1,0},{0,-1},{1,0},{0,1}},flag;void dfs(int x,int y,int dir,int num){ if(flag) return; if(x == endx && y == endy) { flag = 1; return; } if(num == 2) { if(dir == 0||dir == 2) { if(y != endy) return; } else { if(x != endx) return; } } int xx,yy; for(int i = 0;i < 4;i++) { xx = x+dis[i][0]; yy = y+dis[i][1]; if(xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) continue; if(xx == endx && yy == endy || a[xx][yy] == 0) { vis[xx][yy] = 1; if(i == dir) dfs(xx,yy,dir,num); else if(num < 2)dfs(xx,yy,i,num+1); vis[xx][yy] = 0; } }}int main(){ while(cin >> n >> m && n &&m) { flag = 0; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) cin >> a[i][j]; } int num; cin >> num; while(num--) { int beginx,beginy; cin >> beginx >> beginy >> endx >> endy; if(beginx == endx && beginy == endy || a[beginx][beginy] != a[endx][endy] || a[beginx][beginy] == 0) { cout << "NO" << endl; continue; } flag = 0; memset(vis,0,sizeof(vis)); for(int i = 0;i < 4;i++) { if(!flag) dfs(beginx,beginy,i,0); } if(flag) cout << "YES" << endl; else cout << "NO" << endl; } } return 0;}
HDU_1175_dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。