题意:链接
分析:每一个D或者是E点往四面延伸,并且赋一个特殊的值,能看到D点的点赋值为1,能看到E点的点赋值为1000,这是因为最多100步,因此最后可以根据除以1000和对1000取模来得出某个状态的值,那么这个数值对应的状态就有四种,BFS搜索即可。之前没有考虑到折回这种情况,原因就是状态没有进行完全的搜索。后面看了网上的写法中多是直接开设了四维的一个状态,只需记录某状态走还是没走,也就没有这种折回的考虑了。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 105;
int n, m, t;
int sx, sy, dx, dy, ex, ey;
char mp[N][N];
int score[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
struct Node {
int x, y, val, ti;
Node() {}
Node(int _x, int _y, int _val, int _ti) : x(_x), y(_y), val(_val), ti(_ti) {}
};
inline bool judge(int x, int y) {
if (x < 1 || x > n || y < 1 || y > m) return false;
else return true;
}
inline int cal(int x) {
int a = (int)(bool(x/1000));
int b = (int)(bool(x%1000));
if (a && b) return 3;
else if (a) return 2;
else if (b) return 1;
else return 0;
}
int lol[N][N];
int solve() {
memset(lol, 0xff, sizeof (lol));
queue<Node>q;
q.push(Node(sx, sy, score[sx][sy], t));
lol[sx][sy] = cal(score[sx][sy]);
while (!q.empty()) {
Node tmp = q.front();
q.pop();
if (lol[tmp.x][tmp.y] == 3) return t - tmp.ti;
if (tmp.ti > 0) { // 如果还有剩余时间
for (int k = 0; k < 4; ++k) {
int cx = tmp.x + dir[k][0], cy = tmp.y + dir[k][1];
int cc = cal(tmp.val + score[cx][cy]);
if (judge(cx, cy) && cc != lol[cx][cy] && mp[cx][cy] == '.') {
lol[cx][cy] = cc;
if (lol[cx][cy] == 3) return t-(tmp.ti-1);
q.push(Node(cx, cy, tmp.val+score[cx][cy], tmp.ti-1));
}
}
}
}
return -1;
}
int main() {
int T, ca = 0;
scanf("%d", &T);
while (T--) {
int cx, cy;
scanf("%d %d %d", &n, &m, &t);
memset(score, 0, sizeof (score));
for (int i = 1; i <= n; ++i) {
scanf("%s", mp[i]+1);
for (int j = 1; j <= m; ++j) {
if (mp[i][j] == 'S') {
sx = i, sy = j;
mp[i][j] = '.';
} else if (mp[i][j] == 'D') {
dx = i, dy = j;
} else if (mp[i][j] == 'E') {
ex = i, ey = j;
}
}
}
for (int k = 0; k < 4; ++k) { // 把分数都加到格子上
cx = dx + dir[k][0], cy = dy + dir[k][1];
while (judge(cx, cy) && mp[cx][cy] == '.') {
score[cx][cy] += 1;
cx += dir[k][0], cy += dir[k][1];
}
cx = ex + dir[k][0], cy = ey + dir[k][1];
while (judge(cx, cy) && mp[cx][cy] == '.') {
score[cx][cy] += 1000;
cx += dir[k][0], cy += dir[k][1];
}
}
printf("Case %d:\n%d\n", ++ca, solve());
}
return 0;
}