根据转弯次数和有没有找到答案来剪枝
#include<iostream> #include<cstring> using namespace std; const int N=1010; int n,m,q,x1,y1,x2,y2,flag; int v[N][N],map[N][N]; int direction[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; #define check(x,y) (x>=1&&x<=n&&y>=1&&y<=m) void DFS(int x,int y,int dir,int turn){ if(turn>2 || flag) return ; if(turn==2 && x!=x2 && y!=y2) return ; if(x==x2 && y==y2 && turn<=2){ flag=1; return ; } for(int i=0;i<4;i++){ int nx=x+direction[i][0]; int ny=y+direction[i][1]; if(!check(nx,ny) || v[nx][ny]==1) continue; if(!map[nx][ny] || (nx==x2&&ny==y2)){ v[nx][ny]=1; if(dir==-1||dir==i) DFS(nx,ny,i,turn); else DFS(nx,ny,i,turn+1); v[nx][ny]=0; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); while(cin>>n>>m && n && m){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>map[i][j]; cin>>q; while(q--){ memset(v,0,sizeof(v)); flag=0; cin>>x1>>y1>>x2>>y2; if(map[x1][y1]!=map[x2][y2] || map[x1][y1]==0){ cout<<"NO"<<endl; continue; } DFS(x1,y1,-1,0); if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; }
标签:剪枝,hdu,连连看,map,int,y1,&&,x2,y2 From: https://www.cnblogs.com/accbulb/p/18016118