本文共 4848 字，大约阅读时间需要 16 分钟。
一个人要从一个点走到一个点，但是有一些护卫。
不同的护卫有一个不一定不同的值，就是这个人不能走到的点是和护卫哈曼顿距离小于这个值的点。 然后这个人有技能，它可以一步走到 d 个外（只能走四面，普通走可以走八方），也可以在一秒内走到原本护卫能看到的地方。（但是还是不可以走到护卫所在的位置） 然后技能可以两个一起用，没有间隔时间，但是都有使用次数的限定。问你能不能走到，如果可以，优先选步数最少的，如果步数最少，优先选使用技能数最少的，如果还一样，就选隐身次数最少的。
如果不能走到，就输出 -1，否则输出步数和两个技能的使用次数。这道题看着就是要 bfs 模拟。
主要的算法问题就是怎么看这个地方会不会被护卫看到。
那我们看到哈曼顿距离，以及它的图形：* * * * * * * * * * * * *
我们可以发现，我们可以用差分来做。
枚举每一行，然后进行差分。最后我们把序列还原回去，就可以得到一个点会被多少个护卫看到了。
接着就是代码方面，这一题也是非常的烦人。
首先，就算隐身了，你也不可以走到有护卫的位置。 第二，因为你的状态包含了你用两个技能的次数，所以我们不能记录是否到过这个点，而是应该记录是否在两个技能的使用次数分别为哪两个值的时候到过这个点。 第三，因为你上面这样一搞，时间会比较长，为了减少时间，我们进行一个剪枝：如果现在的步数比当前最优答案所需步数还多，就直接退出。（因为你比较答案谁更优的第一条件就是比步数）#include#include #include #include using namespace std;struct xx { int x, y, bc, hind, rush;}now;int n, m, c1, c2, d, a[401][401], sx, sy, tx, ty, b[401][401], ans = -1, hind, rush;int dx[4] = { 0, 0, 1, -1}, dy[4] = { 1, -1, 0, 0}, edx[4] = { 1, 1, -1, -1}, edy[4] = { 1, -1, 1, -1};bool realnot[401][401], in[401][401][16][16];queue q;char c;bool ch(int x, int y) { //判断是否走出边界 if (x < 1 || x > n) return 0; if (y < 1 || y > m) return 0; return 1;}bool bin(xx x) { //之前有没有到过 if (in[x.x][x.y][x.hind][x.rush]) return 0; in[x.x][x.y][x.hind][x.rush] = 1; return 1;}void bfs() { q.push((xx){ sx, sy, 0, 0, 0}); while (!q.empty()) { now = q.front(); q.pop(); if (now.bc > ans && ans != -1) continue;//剪枝，如果距离已经比已知的最优答案还长 if (now.x == tx && now.y == ty) { //到终点 if (ans == -1) { //第一次到 ans = now.bc; hind = now.hind; rush = now.rush; } else if (now.bc < ans) { //距离更短 ans = now.bc; hind = now.hind; rush = now.rush; } else if (now.bc == ans) { if (now.hind + now.rush < hind + rush) { //距离相等的同时技能使用次数更少 hind = now.hind; rush = now.rush; } else if (now.hind + now.rush == hind + rush) { if (now.hind < hind) { //上述条件都相等的同时隐身用的更少 hind = now.hind; rush = now.rush; } } } } for (int i = 0; i < 4; i++) { if (ch(now.x + dx[i], now.y + dy[i])) { if (!b[now.x + dx[i]][now.y + dy[i]]) { //普通走 if (bin((xx){ now.x + dx[i], now.y + dy[i], now.bc + 1, now.hind, now.rush})) q.push((xx){ now.x + dx[i], now.y + dy[i], now.bc + 1, now.hind, now.rush}); } else if (now.hind < c1 && !realnot[now.x + dx[i]][now.y + dy[i]]) { //隐身 if (bin((xx){ now.x + dx[i], now.y + dy[i], now.bc + 1, now.hind + 1, now.rush})) q.push((xx){ now.x + dx[i], now.y + dy[i], now.bc + 1, now.hind + 1, now.rush}); } } if (ch(now.x + edx[i], now.y + edy[i])) { if (!b[now.x + edx[i]][now.y + edy[i]]) { //普通走（斜着走） if (bin((xx){ now.x + edx[i], now.y + edy[i], now.bc + 1, now.hind, now.rush})) q.push((xx){ now.x + edx[i], now.y + edy[i], now.bc + 1, now.hind, now.rush}); } else if (now.hind < c1 && !realnot[now.x + edx[i]][now.y + edy[i]]) { //隐身（斜着走） if (bin((xx){ now.x + edx[i], now.y + edy[i], now.bc + 1, now.hind + 1, now.rush})) q.push((xx){ now.x + edx[i], now.y + edy[i], now.bc + 1, now.hind + 1, now.rush}); } } if (now.rush < c2 && ch(now.x + d * dx[i], now.y + d * dy[i])) { if (!b[now.x + d * dx[i]][now.y + d * dy[i]]) { if (bin((xx){ now.x + d * dx[i], now.y + d * dy[i], now.bc + 1, now.hind, now.rush + 1})) q.push((xx){ now.x + d * dx[i], now.y + d * dy[i], now.bc + 1, now.hind, now.rush + 1}); }//闪现 else if (now.hind < c1 && !realnot[now.x + d * dx[i]][now.y + d * dy[i]]) { if (bin((xx){ now.x + d * dx[i], now.y + d * dy[i], now.bc + 1, now.hind + 1, now.rush + 1})) q.push((xx){ now.x + d * dx[i], now.y + d * dy[i], now.bc + 1, now.hind + 1, now.rush + 1}); }//闪现加隐身 } } }}int main() { scanf("%d %d %d %d %d", &n, &m, &c1, &c2, &d); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { c = getchar(); while (c != '.' && (c < '0' || c > '9') && c != 'S' && c != 'T') c = getchar(); if (c == '.') a[i][j] = -1; else if (c >= '0' && c <= '9') { realnot[i][j] = 1; a[i][j] = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { a[i][j] = a[i][j] * 10 + c - '0'; c = getchar(); } a[i][j]--;//要的是哈曼顿距离小于x的，那就是小于等于x-1的 for (int k = max(1, i - a[i][j]); k <= min(n, i + a[i][j]); k++) { b[k][max(1, j - (a[i][j] - abs(i - k)))]++; b[k][min(m, j + (a[i][j] - abs(i - k))) + 1]--; } } else if (c == 'S') { a[i][j] = -1; sx = i; sy = j; } else if (c == 'T') { a[i][j] = -1; tx = i; ty = j; } } for (int i = 1; i <= n; i++)//还原差分数组 for (int j = 1; j <= m; j++) b[i][j] += b[i][j - 1]; bfs(); if (ans == -1) { printf("-1"); return 0; } printf("%d %d %d", ans, hind, rush); return 0;}
转载地址：http://iivh.baihongyu.com/