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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
| #include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
int n;
char arr[60][60]; //存放棋子
bool attack[2][60][60]; //某点是否可以被攻击（第一维没有用处，只用了第一维的1）
int dp[60][60];
int O_x, O_y, X_x_pos, X_y_pos;
int K_x[8] = {1,2,2,1,-1,-2,-2,-1};
int K_y[8] = {2,1,-1,-2,-2,-1,1,2};
int X_x[8] = {-1,0,1,-1,1,-1,0,1};
int X_y[8] = {-1,-1,-1,0,0,1,1,1};
inline void render(int x, int y, int no){ //针对坐标为(x,y)的棋子在attack数组中绘制出攻击范围
switch (arr[x][y]){
case 'C'://城堡
for (int i = x + 1; i <= n; i++){
if (arr[i][y] == '.')attack[no][i][y] = true;
else {
attack[no][i][y] = true;
break;
}
}
for (int i = x - 1; i >= 1; i--){
if (arr[i][y] == '.')attack[no][i][y] = true;
else {
attack[no][i][y] = true;
break;
}
}
for (int i = y + 1; i <= n; i++){
if (arr[x][i] == '.')attack[no][x][i] = true;
else {
attack[no][x][i] = true;
break;
}
}
for (int i = y - 1; i >= 1; i--){
if (arr[x][i] == '.')attack[no][x][i] = true;
else {
attack[no][x][i] = true;
break;
}
}
break;
case 'K'://骑士
for (int i = 0; i < 8; i++){
if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
attack[no][x + K_x[i]][y + K_y[i]] = true;
}
}
break;
case 'B'://主教
for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
else {
attack[no][x + i][y - i] = true;
break;
}
}
for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
else{
attack[no][x + i][y + i] = true;
break;
}
}
for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
else{
attack[no][x - i][y + i] = true;
break;
}
}
for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
else{
attack[no][x - i][y - i] = true;
break;
}
}
break;
case 'Q'://皇后
//城堡
for (int i = x + 1; i <= n; i++){
if (arr[i][y] == '.')attack[no][i][y] = true;
else {
attack[no][i][y] = true;
break;
}
}
for (int i = x - 1; i >= 1; i--){
if (arr[i][y] == '.')attack[no][i][y] = true;
else {
attack[no][i][y] = true;
break;
}
}
for (int i = y + 1; i <= n; i++){
if (arr[x][i] == '.')attack[no][x][i] = true;
else {
attack[no][x][i] = true;
break;
}
}
for (int i = y - 1; i >= 1; i--){
if (arr[x][i] == '.')attack[no][x][i] = true;
else {
attack[no][x][i] = true;
break;
}
}
//主教
for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
else {
attack[no][x + i][y - i] = true;
break;
}
}
for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
else{
attack[no][x + i][y + i] = true;
break;
}
}
for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
else{
attack[no][x - i][y + i] = true;
break;
}
}
for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
else{
attack[no][x - i][y - i] = true;
break;
}
}
break;
case 'X'://国王
for (int i = 0; i < 8; i++){
if (x + X_x[i]>0 && x + X_x[i] <= n&&y + X_y[i] > 0 && y + X_y[i] <= n){
attack[no][x + X_x[i]][y + X_y[i]] = true;
}
}
break;
case 'P'://普通士兵
if (x - 1 > 0 && x - 1 <= n&&y + 1 > 0 && y + 1 <= n){
attack[no][x - 1][y + 1] = true;
}
if (x + 1 > 0 && x + 1 <= n&&y + 1 > 0 && y + 1 <= n){
attack[no][x + 1][y + 1] = true;
}
break;
}
}
inline void render_all(){//将地图上的所有点全部重绘
memset(attack, false, sizeof(attack));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
switch (arr[i][j]){
case 'O'://标记好白骑士的起始点
O_x = i;
O_y = j;
break;
case '.':
case '\0':
break;
case 'X'://黑国王的终止点
X_x_pos = i;
X_y_pos = j;
default:
render(i, j, 1);
}
}
}
}
void dfs(int x, int y,int step){//记忆化dfs
if (x <= 0 || y <= 0 || x > n || y > n)return; //超出边界的情况
if (arr[x][y] == 'X'){ //dfs到了黑国王
if (step < dp[x][y])dp[x][y] = step;
return;
}
if (attack[1][x][y])return; //刚跳到坐标x,y就被攻击了
if (step>=dp[x][y])return; //注意，这里是重点，也是为什么DFS不会超时的原因，因为我写的这个DFS记忆化不满足无后效性，所以只要走到一点后，当前步数大于之前走到过这里的最小步数就可以退出了。
dp[x][y] = step;
if (arr[x][y] != '.'){ //该格子上有棋子
char ch = arr[x][y];
arr[x][y] = '.';
render_all(); //把棋子吃掉以后重新绘制攻击情况
for (int i = 0; i < 8; i++){
if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
dfs(x + K_x[i], y + K_y[i], step + 1);
}
}
arr[x][y] = ch; //回溯
render_all();
}
else{ //该格子上无棋子
for (int i = 0; i < 8; i++){
if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
dfs(x + K_x[i], y + K_y[i], step + 1);
}
}
}
}
int main(){
ios::sync_with_stdio(false); //加快cin速度
while (cin >> n){ //多组数据
memset(arr, 0, sizeof(arr));
memset(attack, false, sizeof(attack));
memset(dp, 0x7f, sizeof(dp));
for (int i = 1; i <= n; i++){
cin >> arr[i] + 1;
}
render_all(); //先进行整幅地图攻击情况的绘制
dfs(O_x, O_y, 0);
if (dp[X_x_pos][X_y_pos] == 0x7f7f7f7f){
cout << -1 << endl;
}
else{
cout << dp[X_x_pos][X_y_pos] << endl;
}
}
return 0;
} |