题意比较啰嗦。
就是搜索加上一些特殊的条件，比如可以在原地不动，也就是在原地呆一秒，如果有监控也可以花3秒的时间走过去。
这种类型的题目还是比较常见的。以下代码b[i][j][x]表示格子i行j列在x时刻有监控照的到。因为只有4个方向，所以只需要时间对4取模就行。具体细节见代码。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = ;
const int dx[] = {, , , -, }, dy[] = {, -, , , };
char mp[maxn][maxn];
int b[maxn][maxn][];
int T, n, kase;
bool vis[maxn][maxn][];
struct Node {
int x, y, step;
bool operator < (const Node &b) const {
return step > b.step;
}
};
Node tar;
int bfs(int x, int y)
{
memset(vis, false, sizeof(vis));
priority_queue<Node> Q;
Node cur, nex;
cur.x = x; cur.y = y; cur.step = ;
vis[x][y][] = true;
Q.push(cur);
while (!Q.empty())
{
cur = Q.top(); Q.pop();
if (tar.x == cur.x && tar.y == cur.y) return cur.step;
for (int i = ; i < ; i++)//最后一个状态是可以呆在原地不动
{
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx < || ny < || nx >= n || ny >= n) continue;
if (mp[nx][ny] == '#') continue;
nex = cur;
if (b[nx][ny][cur.step % ] || b[cur.x][cur.y][cur.step % ])//如果下一个位置有监控或者当前这个位置监控的到
{
if (nx == cur.x && ny == cur.y && !vis[nx][ny][(cur.step + ) % ])//如果当前这个位置监控的到,
{
nex.step++;
vis[nx][ny][nex.step % ] = true;
Q.push(nex);
}
else if (!vis[nx][ny][(cur.step + ) % ])//如果下一个监控的到
{
nex.x = nx; nex.y = ny;
nex.step += ;
vis[nx][ny][nex.step % ] = true;
Q.push(nex);
}
}
else if (!vis[nx][ny][(cur.step + ) % ])//否则直接走
{
nex.x = nx; nex.y = ny; nex.step++;
vis[nx][ny][nex.step % ] = true;
Q.push(nex);
}
}
}
return -;
}
int main()
{
scanf("%d", &T);
while (T--)
{
int x, y;
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%s", mp[i]);
memset(b, , sizeof(b));
for (int i = ; i < n; i++)
{
for (int j = ; j < n; j++)
{
if (mp[i][j] == 'M')
{
x = i; y = j;
}
else if (mp[i][j] == 'N')
{
b[i][j][] = b[i][j][] = b[i][j][] = b[i][j][] = ;//它本身这个位置不管任意时刻都被监控到
if (i - >= ) b[i - ][j][] = ;//表示紧挨着它上面的那个在1秒的时候被监控到
if (j + < n) b[i][j + ][] = ;//紧挨着它右边的在第2秒的时候,意思就是下一秒
if (i + < n) b[i + ][j][] = ;//下两秒
if (j - >= ) b[i][j - ][] = ;//下三秒在忘左边的位置被监控的到
}
else if (mp[i][j] == 'E')
{
b[i][j][] = b[i][j][] = b[i][j][] = b[i][j][] = ;
if (i - >= ) b[i - ][j][] = ;
if (j + < n) b[i][j + ][] = ;
if (i + < n) b[i + ][j][] = ;
if (j - >= ) b[i][j - ][] = ;
}
else if (mp[i][j] == 'S')
{
b[i][j][] = b[i][j][] = b[i][j][] = b[i][j][] = ;
if (i - >= ) b[i - ][j][] = ;
if (j + < n) b[i][j + ][] = ;
if (i + < n) b[i + ][j][] = ;
if (j - >= ) b[i][j - ][] = ;
}
else if (mp[i][j] == 'W')
{
b[i][j][] = b[i][j][] = b[i][j][] = b[i][j][] = ;
if (i - >= ) b[i - ][j][] = ;
if (j + < n) b[i][j + ][] = ;
if (i + < n) b[i + ][j][] = ;
if (j - >= ) b[i][j - ][] = ;
}
else if (mp[i][j] == 'T')
{
tar.x = i; tar.y = j;
}
}
}
printf("Case #%d: %d\n", ++kase, bfs(x, y));
}
return ;
}