#include<iostream>#include<queue>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int N, M, minstep, sum, msum;char maze[15][15];int vis[15][15];int dx[] = { 0, -1, 0, 1};int dy[] = {-1, 0, 1, 0};typedef struct { int x, y; int step;}State;State begin, end;queue<State> q;int mayreach(int x, int y, int step){ if((int)abs((double)(end.x - x)) + abs(double(end.y - y)) > minstep - step) return 0; return 1;}void dfs(int x, int y, int step, bool mines){ if(x < 0 || x > N-1 || y < 0 || y > M-1) return; if(x == end.x && y == end.y && step == minstep) { if(mines == true) msum++; sum++; } if(maze[x][y] == '#') return; if(!mayreach(x, y, step)) return; if(maze[x][y] == 'M') mines = true; dfs(x, y-1, step + 1, mines); dfs(x, y+1, step + 1, mines); dfs(x-1, y, step + 1, mines); dfs(x+1, y, step + 1, mines);}int main(){ int ncases, i, j, ok, c; scanf("%d", &ncases); getchar(); for(c = 1; c <= ncases; c++) { scanf("%d%d", &N, &M); getchar(); for(i = 0; i < N; i++) { for(j = 0; j < M; j++) { scanf("%c", &maze[i][j]); if(maze[i][j] == 'S') { begin.x = i; begin.y = j; } else if(maze[i][j] == 'T') { end.x = i; end.y = j; } } getchar(); } memset(vis, 0, sizeof(vis)); ok = 0; begin.step = 0; sum = msum = 0; vis[begin.x][begin.y] = 1; q.push(begin); while(!q.empty()) { State u = q.front(); q.pop(); if(u.x == end.x && u.y == end.y) { ok = 1; minstep = u.step; break; } for(i = 0; i < 4; i++) { State v; v.step = u.step + 1; v.x = u.x + dx[i]; v.y = u.y + dy[i]; if(v.x >= 0 && v.x < N && v.y >=0 && v.y < M && maze[v.x][v.y] != '#' && !vis[v.x][v.y]) { q.push(v); vis[v.x][v.y] = 1; } } } dfs(begin.x, begin.y, 0, false); if(!ok || sum == msum) printf("Mission #%d:nMission Impossible.nn", c); else printf("Mission #%d:nThe probability for the spy to get to the telegraph transmitter is %.2lf%%.nn", c, (0.0+sum-msum)*100/sum); while(!q.empty()) q.pop(); } return 0;}
