【BFS】Ybt_荆轲刺秦王

荆轲刺秦王

解

BFS。
注意处理情况的时候细心点。

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int n, m, c1, c2, d, a, qx, qy, zx, zy, ans, ans1, ans2;
int b[500][500], B[500][500][20][20];
int fx[15] = { 0, +1, -1, 0, 0, +1, +1, -1, -1 };
int fy[15] = { 0, 0, 0, +1, -1, -1, +1, -1, +1 };
int f2[15] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };struct asdf {int x, y, c1, c2;
};int get() {	//读入，起点返回-1，终点返回-2，其余返回士兵巡视距离char c = getchar();int l = 0;while ((c > '9' || c < '0') && c != 'S' && c != 'T' && c != '.') c = getchar();if (c == 'S')l = -1;else if (c == 'T')l = -2;elsewhile (c <= '9' && c >= '0') {l = l * 10 + c - 48;c = getchar();}return l;
}void cl(int x, int y, int jl) {  //这里没用差分，直接把士兵能巡查到的地方赋值为1，士兵的位置赋值2for (int i = 0; i <= jl; ++i)for (int j = 0; j <= jl - i; ++j) {if (x + i <= n && y + j <= m)b[x + i][y + j] = max(b[x + i][y + j], 1);if (x - i >= 1 && y + j <= m)b[x - i][y + j] = max(b[x - i][y + j], 1);if (x + i <= n && y - j >= 1)b[x + i][y - j] = max(b[x + i][y - j], 1);if (x - i >= 1 && y - j >= 1)b[x - i][y - j] = max(b[x - i][y - j], 1);}b[x][y] = 2;
}void init() {scanf("%d%d%d%d%d", &n, &m, &c1, &c2, &d);fx[9] = fy[11] = d;fx[10] = fy[12] = -d;for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) {a = get();if (a == -1) qx = i, qy = j;if (a == -2)zx = i, zy = j;if (a > 0) //处理士兵巡查范围cl(i, j, a - 1);}
}bool check(int xx, int yy, int pd1, int pd2) {if (xx < 1 || yy < 1 || xx > n || yy > m || pd1 < 0 || pd2 < 0) //没有超界，没有使用过多的次数return 0;if (B[xx][yy][pd1][pd2] > 0 || b[xx][yy] == 2) //没有走到士兵的位置return 0;return 1;
}void bfs() {queue<asdf> Q;Q.push((asdf){ qx, qy, c1, c2 });  //坐标，以及两种技能的剩余次数B[qx][qy][c1][c2] = 1;while (!Q.empty()) {int x = Q.front().x, y = Q.front().y, j1 = Q.front().c1, j2 = Q.front().c2;Q.pop();for (int i = 1; i <= 12; ++i) {  //8个方向加上4个方向瞬移int mbx = x + fx[i], mby = y + fy[i], j11 = 0, j22 = f2[i];//得出新坐标还有是否消耗瞬移次数if (b[mbx][mby] == 1)  //如果目标点需要隐身，消耗1次隐身j11 = 1;if (check(mbx, mby, j1 - j11, j2 - j22)) { //如果可以走Q.push((asdf){ mbx, mby, j1 - j11, j2 - j22 });B[mbx][mby][j1 - j11][j2 - j22] = B[x][y][j1][j2] + 1;}}}
}void outt() {ans = 100000000;for (int i = 0; i <= c1; ++i)for (int j = 0; j <= c2; ++j)  //枚举剩余次数if (B[zx][zy][i][j]) {if (B[zx][zy][i][j] < ans || (B[zx][zy][i][j] == ans && ans1 + ans2 < i + j) ||(B[zx][zy][i][j] == ans && ans1 + ans2 == i + j && ans1 < i)) {ans = B[zx][zy][i][j]; //按照题目条件打，更替结果ans1 = i;ans2 = j;}}if (ans != 100000000)printf("%d %d %d\n", ans - 1, c1 - ans1, c2 - ans2); //输出步数及各技能使用次数elseprintf("-1\n");
}int main() {init();  //读入bfs();  //处理outt();	//输出
}