P8854 [POI2002] 超级马 题解

这题其实就是搜索，不知道怎么评绿的。

题意

有一个大小无限的棋盘，有一只马，给定 \(n\) 种跳法，判断马是否能跳到棋盘所有点。

题解

搜索马是否可以跳到他上下左右的四个点，因为只要能跳到这四个点，就可以以这四个点为基础跳到其他所有的点。
这里有一些细节需要处理：

• 因为每次操作能是横纵坐标加减 100，所以将马的位置放在（100，100），避免数组越界。

• 每组数据需要清零标记数组。

• 初始搜索是要标记马的初始点位

时间稳过。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,dx[105],dy[105],vis[205][205];
bool ok;
struct M{
	int x,y;
};
void bfs(){
	queue<M>q;
	q.push((M){100,100});//马初始要在(100，100) 
	vis[100][100]=1;
	while(!q.empty()){
		M u=q.front();
		q.pop();
		if(vis[101][100]&&vis[100][101]&&vis[100][99]&&vis[99][100]){//判断周围的四个点是否能到 
			ok=1;
			break;
		}
		for(int i=1;i<=n;i++){
			int nx=u.x+dx[i];
			int ny=u.y+dy[i];
			if(nx>=1&&nx<=200&&ny>=1&&ny<=200&&!vis[nx][ny]){
				q.push((M){nx,ny});
				vis[nx][ny]=1;
			}
		}
	}
	if(vis[101][100]&&vis[100][101]&&vis[100][99]&&vis[99][100]){
		ok=1;
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		for(int i=1;i<=200;i++){//清空数组 
			for(int j=1;j<=200;j++){
				vis[i][j]=0;
			}
		}
		cin>>n;
		for(int i=1;i<=n;i++){
			scanf("%d%d",dx+i,dy+i);
		}
		ok=0;
		bfs();
		if(ok)puts("TAK");
		else puts("NIE");
	}
	return 0;
}