一天，蒜头君梦见自己当上了王子，但是不幸的是，自己的公主被可恶的巫婆抓走了。于是蒜头君动用全国的力量得知，自己的公主被巫婆抓进一个迷宫里面。由于全国只有蒜头君自己可以翻越迷宫外的城墙，蒜头君便自己一人走上的拯救自己公主的路途。
碰巧的是巫婆出去了，迷宫也不大，蒜头君可以直接和公主对话，于是两个人便开始相互靠近。每一步移动只能朝着上下左右四个方向走一格，不能走进墙所在的位置。蒜头君救公主心切，一次必须沿着一个方向走两步（允许跨越迷宫中的墙）；公主柔弱，一次只能走一步。问在这个迷宫中，蒜头君是否可以救出公主（蒜头君和公主相遇后，就能背着公主逃出迷宫了）。
输入格式
第一行输入两个整数 n(1≤n≤100), m(1≤m≤100) 表示迷宫的行和列。
然后有一个 n×m 的地图，地图由'.'、'#'、'w'、'g'这四个部分组成。'.'表示可以通行的路，'#'表示迷宫的墙，'w'表示王子开始所在的位置，'g'表示公主开始所在的位置。
输出格式
输出王子是不可以救出自己的公主，如果能救出则输出\"yes\"，否则输出\"no\"。
样例输入
1 8
w....#.g
样例输出
yes
该问题比较复杂，需要两个dfs分别记录王子和公主能到达的位置，然后遍历是否有重合的部分，如果有证明能够逃走。为了方便理解，小编写了两个dfs函数，没有合为一个，并且将王子和公主能到达的位置打印出来。
#include <iostream> using namespace std; int n,m; char a[105][105]; bool wz[105][105]; bool gz[105][105]; void dfsw(int x,int y){ if(x<0 || x>=n || y<0 || y>=m || wz[x][y]==1) { return; } wz[x][y]=1; dfsw(x+2,y); dfsw(x-2,y); dfsw(x,y-2); dfsw(x,y+2); } void dfsg(int x,int y){ if(x<0 || x>=n || y<0 || y>=m || a[x][y]=='#' || gz[x][y]==1){ return; }else{ gz[x][y]=1; dfsg(x+1,y); dfsg(x-1,y); dfsg(x,y+1); dfsg(x,y-1); } } int main(){ int wx,wy,gx,gy; cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='w'){ wx=i; wy=j; } if(a[i][j]=='g'){ gx=i; gy=j; } } } dfsw(wx,wy); dfsg(gx,gy); cout<<"--------------------"<<endl; cout<<"王子能到达的位置:"<<endl; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<wz[i][j]; } cout<<endl; } cout<<endl; cout<<"--------------------"<<endl; cout<<"公主能到达的位置:"<<endl; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<gz[i][j]; } cout<<endl; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(wz[i][j]&&gz[i][j]){ cout<<"yes"; return 0; } } } cout<<"no"; return 0; }
