正经题解｜棋盘对象

题目大意

在一个$N \times N$的棋盘当中，给出象的起点坐标$sx,sy$,求解能否到达终点$ex,ey$，根据是否可以输出YES 或者NO。

思路解析

题目给出了象的移动方式，分别为

左上:$[x-2,y-2]$

右上:$[x-2,y+2]$

左下:$[x+2,y-2]$

右下:$[x+2,y+2]$

我们就可以根据题目意思直接去写一个迷宫类型的深度优先搜索，走迷宫，判断是否可以到达终点即可。

代码演示

#include<bits/stdc++.h>
using namespace std;
int dir_x[4] = {2,2,-2,-2};
int dir_y[4] = {-2,2,2,-2}; // 方向数组寻找下一个道路

bool vis[505][505]; // 标记数组避免陷入死循环
int n,sx,sy,ex,ey;
bool flag ;

void dfs(int x,int y){
	if(x == ex && y == ey){
		flag = true;
		return ;
	}
	for(int i = 0 ; i < 4 ; i ++ ){
		int tx = x + dir_x[i];
		int ty = y + dir_y[i];
		if(tx >= 1 && ty >= 1 && tx <= n && ty <= n && !vis[tx][ty]){
			vis[tx][ty] = true;
			dfs(tx,ty);
		}
	}
}

int main(){
	
	cin >> n;
	cin >> sx >> sy >> ex >> ey;
	dfs(sx,sy);
	if(flag)cout << "YES" << endl;
	else cout <<"NO" << endl;
	return 0;
}