<题目链接>
题目大意：
在一个棋盘上给定一个起点和终点，判断这两点是否能通过连线连起来，规定这个连线不能穿过其它的棋子，并且连线转弯不能超过2次。
解题分析：
就是DFS从起点开始搜索，只不过搜索的时候需要记录当前的方向和已经转弯的次数，然后通过题目给定的限制条件进行搜索，判断是否存在从起点到终点转弯次数不超过2次的连线。同时，在转弯次数达到两次的时候，我们可以对搜索树进行可行性剪枝，直接判断转弯两次后，该点与终点是否在同一条直线上，从而减少搜索时间。
#include <bits/stdc++.h>
using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++)
const int N= 1e3+;
int mpa[N][N],vis[N][N];
int n,m,sx,sy,ex,ey;
const int dir[][]={,,,,-,,,-};
bool fp; void dfs(int x,int y,int nowdir,int cnt){
vis[x][y]=;
if(cnt>||fp)return;
if(x==ex&&y==ey){ fp=true;return; }
for(int k=;k<;k++){
int cnt1=cnt;
int nx=x+dir[k][],ny=y+dir[k][];
if(nx<||nx>n||ny<||ny>m||vis[nx][ny])continue;
if((nx==ex&&ny==ey)||!mpa[nx][ny]){
if((nowdir!=-)&&nowdir!=k){
cnt1++;if(cnt1==){
if((nx-ex)!=&&(ny-ey)!=)return; //如果第二次转弯与终点不在同一条直线上
else{ //转了2次后，判断该点是否能够通过这条直线到达终点
int xx=nx,yy=ny;
while(xx>=||xx<=n||yy>=||yy<=m){
if(xx==ex&&yy==ey){ fp=true; return; } //如果通过该直线能够直接到达终点
if(mpa[xx][yy]!=)return; //如果中途除终点外有障碍物
xx=xx+dir[k][],yy=yy+dir[k][]; //沿着这条直线往前走
}
}
}
}
dfs(nx,ny,k,cnt1);
}
}
} int main(){
while(~scanf("%d%d",&n,&m),n||m){
rep(i,,n) rep(j,,m) scanf("%d",&mpa[i][j]);
int q;scanf("%d",&q);
while(q--){
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
if(sx<||sx>n||sy<||sy>m||ex<||ex>n||ey<||ey>m||(sx==ex&&sy==ey)){puts("NO");continue;} //判断这两点的位置合不合法
fp=false;
memset(vis,,sizeof(vis));
if(mpa[sx][sy]==mpa[ex][ey]&&mpa[sx][sy])dfs(sx,sy,-,); //如果起点终点相同，且有棋子
fp?puts("YES"):puts("NO");
}
}
}
WA代码
AC代码：
#include <bits/stdc++.h>
using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++)
const int N = 1e3+;
int mpa[N][N];
bool vis[N][N];
int n,m,q,sx,sy,ex,ey;
bool flag;
const int dicx[]={,-,,};
const int dicy[]={,,,-}; void dfs(int x,int y,int dic,int cnt){
if(cnt>||flag) return; //转弯次数大于2或者已经找到就终止
if(cnt==&&(x-ex)!=&&(y-ey)!=) return;//剪枝：判断两次转弯后是否与目标在同一直线上
if(x==ex&&y==ey){ flag=true;return; }
for(int k=;k<;++k){
int xx=x+dicx[k],yy=y+dicy[k];
if(xx<||xx>n||yy<||yy>m||vis[xx][yy]) continue;
if(mpa[xx][yy]==||(xx==ex&&yy==ey)){
vis[xx][yy]=;
if(dic==-||dic==k)dfs(xx,yy,k,cnt);
else dfs(xx,yy,k,cnt+);
vis[xx][yy]=;
}
}
}
int main(){
while(~scanf("%d%d",&n,&m),n||m){
rep(i,,n) rep(j,,m) scanf("%d",&mpa[i][j]);
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
memset(vis,,sizeof(vis));
flag=false;
if(mpa[sx][sy]==mpa[ex][ey]&&mpa[sx][sy])dfs(sx,sy,-,); //初始方向置为-1
flag?puts("YES"):puts("NO");
}
}
}