#include <iostream> #include <cstdio> #include <vector> #include <map> #include <cstring> #include <cstdio> #include <algorithm> #include <set> #include <queue> #include <stack> #include <cstdlib> #include <string> #include <list> #include <bitset> #include <iomanip> #include <cmath> #include <sstream> #include <deque> #include <climits> #include <cassert> using namespace std; #define ull unsigned long long #define ll long long #define Max(x,y) ((x)>(y)?(x):(y)) #define Min(x,y) ((x)<(y)?(x):(y)) #define Sl(x) scanf("%lld",&x) #define Su(x) scanf("%llu",&x) #define S(x) scanf("%d",&x) #define IS(x) cin>>x #define ISF(x) getline(cin,x) #define pii pair<int,int> #define pll pair<ll,ll> #define pps pair<ll,pll> #define ppf pair<pll,ll> #define psi pair<string,int> #define pis pair<int,string> #define fr first #define se second #define MOD 1000000007 #define MP(x,y) make_pair(x,y) #define eps 1e-7 #define V(x) vector<x> #define pb(x) push_back(x) #define mem(x,i) memset(x,i,sizeof(x)) #define fori(i,s,n) for(i=(s);i<(n);i++) #define ford(i,s,n) for(i=(n);i>=(s);--i) #define INF 8944674407370955161LL #define debug(i,st,arr) fori(i,0,st){cout<<arr[i]<<" ";}cout<<endl; #define forci(i,sw) for((i)=(sw).begin();(i)!=(sw).end();(i)++) #define forcd(i,sw) for((i)=(sw).rbegin();(i)!=(sw).rend();(i)++) int abs(int x) {if(x < 0) return -x; return x;} map<pii, int> m1; char a[101][101]; int vis[101][101]; int path[15][15]; int sx, sy, n, m, sk, fk; bool f[15]; int ans; void func (int nw, int k, int n, int curr) { if (n == k) { if (curr + path[nw][fk] < ans) { ans = path[nw][fk] + curr; } return; } for (int i = 0; i < k + 1; i++) { if (i != fk && !f[i]) { f[i] = true; func (i, k, n + 1, curr + path[nw][i]); f[i] = false; } } } bool check(int x, int y) { if(vis[x][y] != 0 || x < 0 || y < 0 || x >= n || y >= m || a[x][y] == '#') return false; return true; } void bfs() { queue<pair<int, int> > q; q.push(pii(sx, sy)); int c = 0; while (!q.empty()) { pii pr = q.front(); q.pop(); if(check(pr.fr + 1, pr.se)) { q.push(pii(pr.fr+1, pr.se)); vis[pr.fr+1][pr.se] = vis[pr.fr][pr.se]+1; } if(check(pr.fr - 1, pr.se)) { q.push(pii(pr.fr-1, pr.se)); vis[pr.fr-1][pr.se] = vis[pr.fr][pr.se]+1; } if(check(pr.fr, pr.se + 1)) { q.push(pii(pr.fr, pr.se+1)); vis[pr.fr][pr.se+1] = vis[pr.fr][pr.se]+1; } if(check(pr.fr, pr.se-1)) { q.push(pii(pr.fr, pr.se-1)); vis[pr.fr][pr.se-1] = vis[pr.fr][pr.se]+1; } } for (map<pii, int>::iterator it = m1.begin(); it != m1.end(); it++) { path[m1[pii(sx, sy)]][it->second] = path[it->second][m1[pii(sx, sy)]] = vis[it->first.first][it->first.second] - 1; } } int main() { int t, k; cin >> t; while (t--) { cin >> n >> m; k = 0; m1.clear(); for (int i = 0; i < 15; i++) { for (int j = 0; j < 15; j++) { path[i][j] = 99999999; } } for (int i = 0; i < n; i++) { scanf("%s", a[i]); for (int j = 0; j < m; j++) { if (a[i][j] == 'W' || a[i][j] == 'T' || a[i][j] == 'C') { m1[pii(i, j)] = k++; //cout << i << " " << j << " " << k - 1 <<endl; } if (a[i][j] == 'T') { sk = k-1; } if (a[i][j] == 'W') { fk = k-1; } } } for (map<pii, int>::iterator it = m1.begin(); it != m1.end(); it++) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) vis[i][j] = 0; } sx = it->first.first; sy = it->first.second; vis[sx][sy] = 1; bfs(); } bool f1 = false; for (int i = 0; i < k; i++) { for (int j = 0; j < i; j++) { if (path[i][j] == -1) { f1 = true; break; } } if(f1) break; } if (f1) { cout << "Mission Failed!\n"; continue; } else { if (k == 2) { cout << path[fk][sk] << endl; } else { memset(f, 0, sizeof(f)); ans = 99999999; f[fk] = f[sk] = true; for (int i = 0; i < k; i++) { if(i != sk && i != fk) { func(i, k - 1, 1, path[sk][i]); } } cout << ans << endl; } } } return 0; }
4 3 3 TCC CCC CCW 100 100 T..................................................................................................C .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... C..................................................................................................W 100 100 T................................................C.................................................C .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... C................................................C.................................................C .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... C................................................C.................................................W 100 100 T................................................C.................................................C .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .....................C.............................................................................. .................................................................................................... .............................................................................C...................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... C................................................C.................................................C .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .....................C.............................................................................. .................................................................................................... .................................................................................................... ............................................................................C....................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... C................................................C.................................................W