Luogu-P3930-一道大水题 Knight

Posted on Edited on Word count in article: 1k

题目 P3930 SAC E#1 - 一道大水题 Knight

题目背景

毒奶色和F91是好朋友。

题目描述

他们经常在一起玩一个游戏，不，不是星际争霸，是国际象棋。

毒奶色觉得F91是一只鸡。他在一个n×n的棋盘上用黑色的城堡（车）、骑士（马）、主教（象）、皇后（副）、国王（帅）、士兵（卒）摆了一个阵。

然而F91觉得毒奶色是一只鸡。他发起了挑战：他要操纵一个白色骑士，不经过任何一个棋子的攻击范围（F91可以连续行动，而毒奶色的棋子不会动，除非白骑士进入了对方的攻击范围），并击杀毒奶色的国王（即进入黑国王所在的位置）。

请告诉F91他最少需要多少步骤来完成这一项壮举。

注意：

1.当F91的白骑士走到毒奶色的棋子所在的格子上的时候，会击杀（吃掉）该棋子。这个棋子也就不再对F91的白骑士有威胁了。

2.如果白骑士开场就在黑子的攻击范围内，则立刻被击杀、F91立刻失败。

3.即使白骑士在攻击王的瞬间进入了其他棋子攻击范围（即其他棋子“看护”着王所在的格子），依然算F91获胜。

攻击范围：

城堡：横、竖方向所有位置，直到被一个其他棋子阻拦。

1
2
3
4
5
..#..
..#..
##C##
..#..
..#..

骑士：横2竖1或者横1竖2的所有位置（最多8个，类似日字）。

1
2
3
4
5
.#.#.
#...#
..K..
#...#
.#.#.

主教：斜向（45°）所有位置，直到被一个其他棋子阻拦。

1
2
3
4
5
#...#
.#.#.
..B..
.#.#.
#...#

皇后：城堡和主教的结合体（既能横/竖向攻击，也能45°角斜向攻击，直到被其他棋子阻挡）。

1
2
3
4
5
#.#.#
.###.
##Q##
.###.
#.#.#

国王：身边8连通位置的8个格子。

1
2
3
4
5
.....
.###.
.#X#.
.###.
.....

士兵：左下方/右下方（45°）的格子（最多2个）。

1
2
3
4
5
.....
.....
..P..
.#.#.
.....

其中字母表示棋子类型，参考输入格式。

‘#’表示可攻击范围。

输入格式

输入包含多组数据。

每一组数据中，第一行一个整数n表示棋盘规模。

接下来n行，每行一个长度为n的字符串。描述棋盘的格局。

其中：

.表示空

O表示白骑士

C表示黑城堡

K表示黑骑士

B表示黑主教

Q表示黒皇后

X表示黑国王

P表示黑士兵

输出格式

对于每一个测试数据，每行输出一个整数，表示F91的最小步数。

如果无论F91如何行动也无法击杀黑国王，输出-1。

思路：状压、bfs

这题就是复杂一点的搜索，细心点思考就能AC！

为什么用状压

本题涉及到吃子，所以需要考虑不同状态的情况。因为本题中棋子数量 num≤15num \leq 15，所以可以使用状压。

基本定义

建立一个结构体 ChessChess 保存棋子的横纵坐标、种类。

chess[i]chess[i] 表示第 ii 个棋子（从 00 开始）。

statestate 为状态，当它的第 ii 位为 11 时，表示第 ii 个棋子活着。

block[state][x][y]block[state][x][y] 表示状态为 statestate 时，坐标 (x,y)(x,y) 是否安全。

vis[state][x][y]vis[state][x][y] 表示状态为 statestate 时，坐标 (x,y)(x,y) 是否已经走过了。

预处理

状态

如果对 state∈[1,2num−1]state \in [1,2^{num}-1] 都计算一次 blockblock，会TLE。

一种优化方式是只计算用到的状态。

这里使用一个 requestrequest 函数，传入一个状态，计算 blockblock，再用 requestedrequested 数组记录是否访问过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// O(num)
inline int check_chess(int state, int x, int y) {
    for(int i = 0; i < pt; i++) {
        Chess &c = chess[i];
        if(!(state & (1 << i))) continue;
        if(c.x == x && c.y == y) return i;
    }
    return -1;
}

// O(num)
inline bool check_attack(int state, int x, int y) {
    if(x < 1 || x > n || y < 1 || y > n) return false;
    return check_chess(state, x, y) == -1;
}

// O((2^num) * num * n)
void request(int state) {
    requested[state] = true;
    for(int x = 0; x < pt; x++) {
        if(!((state) & (1 << x))) continue;
        Chess &c = chess[x];
        switch(c.type) {
            case 'P':
                block[state][c.x + 1][c.y - 1] = true;
                block[state][c.x + 1][c.y + 1] = true;
                break;
            case 'K':
                for(int i = 0; i < 8; i++)
                    block[state][c.x + dx[i]][c.y + dy[i]] = true;
                break;
            case 'C':
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + c_dx[i] * j, c.y + c_dy[i] * j)) break;
                        block[state][c.x + c_dx[i] * j][c.y + c_dy[i] * j] = true;
                    }
                }
                break;
            case 'B':
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + b_dx[i] * j, c.y + b_dy[i] * j)) break;
                        block[state][c.x + b_dx[i] * j][c.y + b_dy[i] * j] = true;
                    }
                }
                break;
            case 'Q':
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + c_dx[i] * j, c.y + c_dy[i] * j)) break;
                        block[state][c.x + c_dx[i] * j][c.y + c_dy[i] * j] = true;
                    }
                }
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + b_dx[i] * j, c.y + b_dy[i] * j)) break;
                        block[state][c.x + b_dx[i] * j][c.y + b_dy[i] * j] = true;
                    }
                }
                break;
            case 'X':
                block[state][c.x + 1][c.y] = true;
                block[state][c.x - 1][c.y] = true;
                block[state][c.x][c.y + 1] = true;
                block[state][c.x][c.y - 1] = true;
                block[state][c.x + 1][c.y + 1] = true;
                block[state][c.x - 1][c.y - 1] = true;
                block[state][c.x - 1][c.y + 1] = true;
                block[state][c.x + 1][c.y - 1] = true;
                break;
        }
    }
}

清空

由于本题涉及多测试点，所以每次计算之后都要清空。

搜索

首先需要特判，如果棋子所在的位置已经是不安全的，直接返回 −1-1。

1
if(block[(1 << pt) - 1][sx][sy]) return -1;

搜索过程中，需要判断是否吃掉了棋子，切换状态。

1
2
3
4
5
6
int ch = check_chess(n.state, nx, ny);
int new_state = n.state;
if(~ch) {
    new_state = n.state ^ (1 << ch); // Eat
}
if(!requested[new_state]) request(new_state);

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// template v9
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 56;

bool block[1 << 16][N][N];

bool requested[1 << 16];

bool vis[1 << 16][N][N];

struct Chess {
    int x, y;
    char type;
} chess[20];

int pt = 0;

struct node {
    int x, y;
    int state;
    int step;
};

queue<node> q;
int n;

int sx, sy, ex, ey;

int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};

int c_dx[] = {0, 1, 0, -1};
int c_dy[] = {1, 0, -1, 0};

int b_dx[] = {1, 1, -1, -1};
int b_dy[] = {1, -1, -1, 1};

inline bool win(int x, int y) {
    return x == ex && y == ey;
}

inline bool invalid(int x, int y) {
    return (x < 1 || x > n || y < 1 || y > n);
}

// O(num)
inline int check_chess(int state, int x, int y) {
    for(int i = 0; i < pt; i++) {
        Chess &c = chess[i];
        if(!(state & (1 << i))) continue;
        if(c.x == x && c.y == y) return i;
    }
    return -1;
}

// O(num)
inline bool check_attack(int state, int x, int y) {
    if(x < 1 || x > n || y < 1 || y > n) return false;
    return check_chess(state, x, y) == -1;
}

// O((2^num) * num * n)
void request(int state) {
    requested[state] = true;
    for(int x = 0; x < pt; x++) {
        if(!((state) & (1 << x))) continue;
        Chess &c = chess[x];
        switch(c.type) {
            case 'P':
                block[state][c.x + 1][c.y - 1] = true;
                block[state][c.x + 1][c.y + 1] = true;
                break;
            case 'K':
                for(int i = 0; i < 8; i++)
                    block[state][c.x + dx[i]][c.y + dy[i]] = true;
                break;
            case 'C':
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + c_dx[i] * j, c.y + c_dy[i] * j)) break;
                        block[state][c.x + c_dx[i] * j][c.y + c_dy[i] * j] = true;
                    }
                }
                break;
            case 'B':
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + b_dx[i] * j, c.y + b_dy[i] * j)) break;
                        block[state][c.x + b_dx[i] * j][c.y + b_dy[i] * j] = true;
                    }
                }
                break;
            case 'Q':
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + c_dx[i] * j, c.y + c_dy[i] * j)) break;
                        block[state][c.x + c_dx[i] * j][c.y + c_dy[i] * j] = true;
                    }
                }
                for(int i = 0; i < 4; i++) {
                    for(int j = 1;; j++) {
                        if(!check_attack(state, c.x + b_dx[i] * j, c.y + b_dy[i] * j)) break;
                        block[state][c.x + b_dx[i] * j][c.y + b_dy[i] * j] = true;
                    }
                }
                break;
            case 'X':
                block[state][c.x + 1][c.y] = true;
                block[state][c.x - 1][c.y] = true;
                block[state][c.x][c.y + 1] = true;
                block[state][c.x][c.y - 1] = true;
                block[state][c.x + 1][c.y + 1] = true;
                block[state][c.x - 1][c.y - 1] = true;
                block[state][c.x - 1][c.y + 1] = true;
                block[state][c.x + 1][c.y - 1] = true;
                break;
        }
    }
}

int bfs() {
    if(win(sx, sy)) return 0;
    request((1 << pt) - 1);
    if(block[(1 << pt) - 1][sx][sy]) return -1;
    vis[(1 << pt) - 1][sx][sy] = true;
    q.push({sx, sy, (1 << pt) - 1, 0});
    while(q.size()) {
        node n = q.front();
        q.pop();
        for(int i = 0; i < 8; i++) {
            int nx = n.x + dx[i], ny = n.y + dy[i];
            if(invalid(nx, ny)) continue; // Out of map
            if(win(nx, ny)) return n.step + 1; // Checkmate
            int ch = check_chess(n.state, nx, ny);
            int new_state = n.state;
            if(~ch) {
                new_state = n.state ^ (1 << ch); // Eat
            }
            if(!requested[new_state]) request(new_state);
            if(block[new_state][nx][ny]) continue; // Eaten
            if(vis[new_state][nx][ny]) continue;
            vis[new_state][nx][ny] = true;
            // printf("%d: (%d, %d)\n", new_state, nx, ny);
            q.push({nx, ny, new_state, n.step + 1});
        }
    }

    return -1;
}

void init() {
    memset(block, 0, sizeof block);
    memset(vis, 0, sizeof vis);
    memset(chess, 0, sizeof chess);
    n = 0;
    pt = 0;
    sx = 0;
    sy = 0;
    ex = 0;
    ey = 0;
    q = queue<node>();
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    init();
    while(cin >> n) {
        char c;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                cin >> c;
                switch(c) {
                    case '.':
                        break;
                    case 'O':
                        sx = i, sy = j;
                        break;
                    case 'X':
                        ex = i, ey = j;
                    default:
                        chess[pt] = {i, j, c};
                        pt++;
                        break;
                }
            }
        }
        cout << bfs() << endl;
        cout.flush();
        init();
    }
    return 0;
}

补充

二维 visvis 数组

为什么不能只记录 vis[x][y]vis[x][y]？

因为本题涉及吃子。在吃子之后，可能有一些点需要重复经过，如果不这样可能会WA。

例如：

输入

1
2
3
4
5
4
X...
.P.O
....
..Q.

输出

1
4

就是同一个点经过两次的情况。