题解 P3930 【SAC E#1 - 一道大水题 Knight】
洛谷不能自动识别代码了？
这道题我做的时候担心会wa或者t——结果ce了。
最后发现题目数据特别水，加个特判就能ac。0ms。中间有一些判断棋子会不会死的技巧，所以快一些。
然后吐槽下数据，虽然数据水，但也不能造谣啊，为啥n出现了55？幸亏我一开始就开的60的数组。
#include <iostream>
#include <cstdio>
#include <cstring> //一开始没加但xcode编译的过，结果交上去就ce
#include <queue>
using namespace std;
int n;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, 2, 1, -1, -2}; //骑士周围八个点
int dx2[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy2[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; //国王周围八个点
int qx, qy; //起点坐标
int board[60][60]; //判断单点是否死亡，适用于骑士、国王、士兵的攻击范围
int vis[60][60]; //判断是否访问
int r[60]; //判断棋子所在行是否会受到攻击，适用于皇后、城堡的攻击范围
int c[60]; //这个是判断列，和行基本一样
int le[120];
int ri[120]; //判断两条对角线，适用于皇后和主教
//以上判断变量的含义是该行、列、对角线、单点受到威胁的数量，比如两个城堡同时看守着第i行，那么r[i] = 2
char a[60][60]; //存储棋盘
queue <int> q1;
queue <int> q2;
queue <int> q3;
bool able(int x, int y)
{
if (r[x] || c[y] || le[x+y] || ri[x-y+n] || board[x][y]) return 0; //判断棋子所在位置是否安全，即行、列等是否有威胁。
return 1; //没有威胁就是安全
}
void init()
{
memset(a, 0, sizeof(a));
memset(r, 0, sizeof(r));
memset(c, 0, sizeof(c));
memset(le, 0, sizeof(le));
memset(ri, 0, sizeof(ri));
memset(vis, 0, sizeof(vis));
memset(board, 0, sizeof(board));
while (!q1.empty()) { q1.pop(); q2.pop(); q3.pop(); }
} //全清空
void bfs()
{
q1.push(qx); //起点横坐标
q2.push(qy); //起点纵坐标
q3.push(1); //到达这个点再走一步所需的步数，初始为1
while (!q1.empty()) {
int x = q1.front();
int y = q2.front();
if (vis[x][y]) { //不走回头路，但这样的话其实可以有数据卡掉
q1.pop();
q2.pop();
q3.pop();
continue;
}
vis[x][y] = 1; //标为已访问
for (int i = 0; i < 8; i++) { //向周围8个点扩展
int xx = x+dx[i];
int yy = y+dy[i];
if (xx > n || xx < 1 || yy > n || yy < 1) continue; //不能跳出棋盘
if (vis[xx][yy]) continue;
if (a[xx][yy] == 'C')
if (able(xx, yy)) { //吃掉之后仍然不受威胁就吃
r[xx]--;
c[yy]--; //威胁-1
q1.push(xx);
q2.push(yy);
q3.push(q3.front()+1); //入栈，步数+1
continue;
}
if (a[xx][yy] == 'K')
if (able(xx, yy)) {
for (int k = 0; k < 8; k++) board[xx+dx[k]][yy+dy[k]]--;
q1.push(xx);
q2.push(yy);
q3.push(q3.front()+1);
continue;
} //骑士同理
if (a[xx][yy] == 'B')
if (able(xx, yy)) {
le[xx+yy]--;
ri[xx-yy+n]--;
q1.push(xx);
q2.push(yy);
q3.push(q3.front()+1);
continue;
} //主教同理
if (a[xx][yy] == 'Q')
if (able(xx, yy)) {
r[xx]--;
c[yy]--;
le[xx+yy]--;
ri[xx-yy+n]--;
q1.push(xx);
q2.push(yy);
q3.push(q3.front()+1);
continue;
} //皇后同理，只是威胁减少的更多
if (a[xx][yy] == 'X') {
cout << q3.front() << endl;
return;
} //吃掉国王就输出步数并退出
if (a[xx][yy] == 'P')
if (able(xx, yy)) {
board[xx+1][yy-1]--;
board[xx+1][yy+1]--;
q1.push(xx);
q2.push(yy);
q3.push(q3.front()+1);
continue;
} //士兵同理
if (able(xx, yy)) { //如果这个格子以上都不是，那就是空的格子，判断一下就能不能走就好了
q1.push(xx);
q2.push(yy);
q3.push(q3.front()+1);
}
}
}
cout << -1 << endl; //最后没吃掉国王就输出-1
}
int main(void)
{
while (cin >> n) { //多组数据
init(); //初始化
for (int i = 1; i <= n; i++) {
scanf("%s", a[i]+1); //输入技巧，以字符串形式读入
for (int j = 1; j <= n; j++) {
if (a[i][j] == 'O') { qx = i; qy = j; } //起点
if (a[i][j] == 'C' || a[i][j] == 'Q') { r[i]++; c[j]++; } //城堡、皇后所在行列威胁+1
if (a[i][j] == 'K') for (int k = 0; k < 8; k++) board[i+dx[k]][j+dy[k]]++; //骑士周围8个点威胁+1
if (a[i][j] == 'B' || a[i][j] == 'Q') { le[i+j]++; ri[i-j+n]++; } //主教、皇后所在对角线威胁+1
if (a[i][j] == 'X') for (int k = 0; k < 8; k++) board[i+dx2[k]][j+dy2[k]]++; //国王周围8个点威胁+1
if (a[i][j] == 'P') { board[i+1][j-1]++; board[i+1][j+1]++; } //士兵下面两个点威胁+1
}
}
if (!able(qx, qy)) { cout << -1 << endl; continue; } //如果一开始就受到威胁，就要死。我改掉ce之后因为忘加这个特判wa成80分
bfs(); //实际上应该深搜才不会被卡，但会t。所以广搜——数据好一点其实可以卡掉广搜
}
return 0;
}