题意：
分析：每一个D或者是E点往四面延伸，并且赋一个特殊的值，能看到D点的点赋值为1，能看到E点的点赋值为1000，这是因为最多100步，因此最后可以根据除以1000和对1000取模来得出某个状态的值，那么这个数值对应的状态就有四种，BFS搜索即可。之前没有考虑到折回这种情况，原因就是状态没有进行完全的搜索。后面看了网上的写法中多是直接开设了四维的一个状态，只需记录某状态走还是没走，也就没有这种折回的考虑了。
#include#include #include #include #include #include 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 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;}