题意:骑士只能在8*8的方格中走田字格,就像中国象棋中的“相"一样。在给出n个坏点,表示两个骑士不能再该位置相遇,问:在给出的两个骑士的点,它们能否相遇。
简单的dfs就可以A了,把其中的一个看做起点,另一个看做目的点,稍微要注意一点:走的步数必须为偶数倍,因为他们是同时走的,一个相当于要走两步。
其实该题可以数学分析解决相遇的条件:|x1-x2|%4==0&&|y1-y2|%4==0;
#include<iostream> #include<cstdio> #include<cstring> using namespace std ; const int x_add[]={-2,-2,2,2}; const int y_add[]={2,-2,2,-2}; char map[9][9]; bool vis[9][9]; int xp[3],yp[3]; bool flag; void dfs(int x,int y,int step) { if(x==xp[1]&&y==yp[1]&&step%2==0){ flag=1; return; } if(flag) return; for(int i=0;i<4;i++){ int x1=x+x_add[i],y1=y+y_add[i]; if(vis[x1][y1]) continue; if(x1<0||x1>=8||y1<0||y1>=8) continue; vis[x1][y1]=1; dfs(x1,y1,step+1); } } int main() { int t,cnt; scanf("%d",&t); while(t--){ flag=0; cnt=0; memset(vis,0,sizeof(vis)); for(int i=0;i<8;i++) scanf("%s",map[i]); for(int i=0;i<8;i++){ for(int j=0;j<8;j++){ if(map[i][j]=='K'){ xp[cnt]=i; yp[cnt++]=j; } } } dfs(xp[0],yp[0],0); if(flag) puts("YES"); else puts("NO"); } return 0 ; }