隐式图搜索，多个状态然后减枝。。没看懂李大大所说可以承受是个啥意思。。
做起来实在太累了。。减枝的部分看了别人的代码，发现着实麻烦，不如用优先队列来的痛快=- =还有用优先队列做的= =
主要是$vis[x][y][p][c]$这组状态比较难搞，但是给了优先级（时间短的先出队），事情就好办了。
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
const int maxn = 30;
char g[maxn][maxn];
// c, 0, 1, 2, 3, 4
// blue,w,g,black,r;
struct Node {
int x, y, c, p, t;
Node(int x, int y, int c, int p, int t):x(x), y(y), c(c), p(p), t(t){}
Node(){}
bool operator < (const Node b) const {
return t > b.t;
}
};
Node s, e;
int n, m;
inline int judge(int x, int y)
{
return x >= && x < m && y >= && y < n;
}
bool vis[maxn][maxn][4][5];
void test() {
for(int i = ; i<m ;i++) {
for(int j = ; j <n; j++ ) {
printf("%2c", g[i][j]);
}
cout << endl;
}
}
int dx[] = {-1, , 1, };
int dy[] = {, 1, , -1};
int bfs()
{
priority_queue <Node> q;
Node t, next;
int ans = INF;
q.push(s);
while(!q.empty())
{
t = q.top(), q.pop();
vis[t.x][t.y][t.p][t.c] = 1;
if(t.x == e.x && t.y == e.y && t.c == e.c) return t.t;
for(int i = ; i < 4; i++)
{
next.x = t.x + dx[i];
next.y = t.y + dy[i];
next.c = (t.c+1)%5;
next.p = i;
if(next.p == t.p)
next.t = t.t+1;
else if(abs(next.p-t.p) == 2)
next.t = t.t+3;
else
next.t = t.t+2;
if(g[next.x][next.y] != '#' && !vis[next.x][next.y][next.p][next.c]
&& judge(next.x, next.y))
q.push(next);
}
}
return ans;
}
int main()
{
#ifdef DEBUG
freopen("input", "r", stdin); //从input文件中读入
// freopen("output", "w", stdout); //输出到output文件
#endif
int kase = 1;
while(scanf("%d%d", &m, &n) != EOF)
{
MEM(vis);
if(n == && m == ) break;
for(int i = ; i < m; i++)
scanf("%s", g[i]);
// read
for(int i = ; i < m ;i ++) {
for(int j = ;j < n; j++) {
if(g[i][j] == 'S') s = Node(i, j, 2, , );
else if(g[i][j] == 'T') e = Node(i, j, 2, , );
}
}
int ans = bfs();
if(kase != 1) CR;
printf("Case #%d\n", kase++);
if(ans == INF) puts("destination not reachable");
else printf("minimum time = %d sec\n", ans);
}
return ;
}