HDU1175（dfs+剪枝）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1175

dfs:

定义函数时注意设计参数

本题：dfs(x,y,dic,turns) x,y为当前搜索起点 dic为当前前进方向 turns为当前转弯数

注意初始化及边界情况

注意搜索终止条件

思路: dfs搜索 剪枝：第二次转弯后，判断与目标是否在同一直线上

#include"iostream" #include"cstdio" #include"stdlib.h" #include"cmath" #include"cstring" #include"cstdlib" #include"vector" #include"stack" #include"queue" #include"set" #include"map" #include"algorithm" #include <utility> #include <iomanip> #include <time.h> #include<list> const double PI=acos(-1.0); using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define lowbit(x) x&-x #define inf 0x3f3f3f3f #define pr pair<int,int> typedef pair<char,int> PAIR; struct CmpByValue { bool operator()(const PAIR& lhs, const PAIR& rhs) { return lhs.second > rhs.second; } }; //priority_queue<int,vector<int>,greater<int>> pp; const int mod = 123456789 ; const int M = 1e3 +10 ; const int limt = 1<<20; const int INF = 1e9; typedef long long ll; int maze[1010][1010]; bool vis[1010][1010]; int sx,sy,ex,ey; bool flag; int n,m,q; int dicx[]= {1,-1,0,0}; int dicy[]= {0,0,1,-1}; void dfs(int x,int y,int dic,int turns) { if(turns>2||flag) return;//转弯次数大于2或者已经找到就终止 if(turns==2&&(x-ex)!=0&&(y-ey)!=0) return;//剪枝：判断两次转弯后是否与目标在同一直线上 if(x==ex&&y==ey&&turns<=2) //搜索终点 { flag=1; return; } for(int i=0; i<4; ++i) //搜索四个方向 { int xx=x+dicx[i]; int yy=y+dicy[i]; if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]) continue;//边界情况 if(maze[xx][yy]==0||(xx==ex&&yy==ey)) { vis[xx][yy]=1; if(dic==-1||dic==i)//如果在起点或者同向的情况turns不变及不转向,并将当前方向记为i dfs(xx,yy,i,turns); else dfs(xx,yy,i,turns+1);//否则turns+1 vis[xx][yy]=0; } } return; } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; memset(maze,0,sizeof(maze)); for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) scanf("%d",&maze[i][j]); scanf("%d",&q); for(int i=0; i<q; ++i) { scanf("%d%d%d%d",&sx,&sy,&ex,&ey); memset(vis,0,sizeof(vis)); flag=0;//初始化 if(maze[sx][sy]==maze[ex][ey]&&maze[sx][sy]) dfs(sx,sy,-1,0);//将初始方向设为-1 if(flag) printf("YES\n"); else printf("NO\n"); } } return 0; }