题解

冷知识，本题解由Q群5个汉字5个数字发布。
本题时限很宽松，可以随便乱搞。
我们可以先判断现在的国王是否安全，然后枚举国王的每一步，判断走完该步后是否安全。

注意士兵的移动有诈骗：
兵的移动方式是向前一格，但攻击敌方棋子是斜向的。即兵的运动方向的左前方和右前方。
所以在标记时，我们要标左前方和右前方。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;

bool vis[9][9];
bool first[9][9];
string a[105];
int dir[8][2]{-1, 0, 0, -1, 0, 1, 1, 0, -1, -1, -1, 1, 1, -1, 1, 1};//方向数组
int dir2[8][2]{-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};//马的方向数组
int n, curx, cury;
bool flag1, flag2;

void queen(int x, int y){//皇后
	for(int i = 0; i < 8; i++){
		int xx = x + dir[i][0], yy = y + dir[i][1];
		while(xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8 && !first[xx][yy]){
			vis[xx][yy] = 1;
			xx += dir[i][0], yy += dir[i][1];
		}
	}
}

void pawn(int x, int y){//士兵
	for(int i = 6; i < 8; i++){//左前方和右前方
		int xx = x + dir[i][0], yy = y + dir[i][1];
		if(xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8) vis[xx][yy] = 1;
	}
}

void rook(int x, int y){//车
	for(int i = 0; i < 4; i++){
		int xx = x + dir[i][0], yy = y + dir[i][1];
		while(xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8 && !first[xx][yy]){
			vis[xx][yy] = 1;
			xx += dir[i][0], yy += dir[i][1];
		}
	}
}

void bishop(int x, int y){//象
	for(int i = 4; i < 8; i++){
		int xx = x + dir[i][0], yy = y + dir[i][1];
		while(xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8 && !first[xx][yy]){
			vis[xx][yy] = 1;
			xx += dir[i][0], yy += dir[i][1];
		}
	}
}

void knight(int x, int y){//骑士
	for(int i = 0; i < 8; i++){
		int xx = x + dir2[i][0], yy = y + dir2[i][1];
		if(xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8) vis[xx][yy] = 1;
	}
}

bool check(){
	memset(vis, 0, sizeof(vis));
	memset(first, 0, sizeof(first));
	for(int i = 1; i <= n; i++){
		int y = a[i][1] - 'a' + 1, x = a[i][2] - '0';
		if(a[i][0] == 'K' || (x == curx && y == cury)) continue;//如果是国王或者子被吃就不记录
		first[x][y] = 1;
	}
	for(int i = 1; i <= n; i++){
		int y = a[i][1] - 'a' + 1, x = a[i][2] - '0';
		if(a[i][0] == 'K' || (x == curx && y == cury)) continue;
		if(a[i][0] == 'Q') queen(x, y);
		if(a[i][0] == 'P') pawn(x, y);
		if(a[i][0] == 'R') rook(x, y);
		if(a[i][0] == 'B') bishop(x, y);
		if(a[i][0] == 'N') knight(x, y);
	}
	
	return !(vis[curx][cury]);
}

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++){//输入 
		cin >> a[i];
		int y = a[i][1] - 'a' + 1, x = a[i][2] - '0';
		if(a[i][0] == 'K') curx = x, cury = y;
	}
	
	flag1 = check();//先判断当前有没有被将军 
	for(int i = 0; i < 8; i++){//再判断移动后会不会被将军 
		curx += dir[i][0], cury += dir[i][1];
		if(curx >= 1 && curx <= 8 && cury >= 1 && cury <= 8 && check()) flag2 = 1;
		curx -= dir[i][0], cury -= dir[i][1];
	}
	
	if(flag1 && flag2) cout << "SAFE\n";//输出结果 
	if(flag1 && !flag2) cout << "STALEMATE\n";
	if(!flag1 && flag2) cout << "CHECK\n";
	if(!flag1 && !flag2) cout << "CHECKMATE\n";
	
	//清空 
	flag1 = flag2 = 0;
	for(int i = 1; i <= n; i++){
		a[i].clear();
	}
	memset(vis, 0, sizeof(vis));
	memset(first, 0, sizeof(first));
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve(); 

	return 0;
}

时间复杂度 $O(T\times N\times m\times k)$，其中 $m$ 表示棋盘大小，$k$ 表示移动方向的数量，即 $m=64,k=8$。