Codeforecs-362A Two Semiknights Meet(dfs)

题意：骑士只能在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 ;
}

最后

以上就是威武紫菜为你收集整理的Codeforecs-362A Two Semiknights Meet(dfs)的全部内容，希望文章能够帮你解决Codeforecs-362A Two Semiknights Meet(dfs)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。