洛谷题号：P3930
2017.10.20更新：
有人在洛谷上指出了本程序的错误：测试样例：
5
….X
…..
…..
….B
..O..
存在一种4步的解法。
….4
…..
…3.
….1
..2..
但程序会输出-1。
经过检查，所给出的测试样例中四步解法经过了之前已经经过的点，这种情况是我的程序所无法处理的。因此我的程序存在漏洞，目前还没有想到什么好办法解决。。
原文章：
本来没想着这题能得分，结果这题月赛时竟然80分，后来出题人说有两个点错了，重测就100了。。。/捂脸
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; } |