fork(2) download
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <map>
  5. #include <cstring>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <set>
  9. #include <queue>
  10. #include <stack>
  11. #include <cstdlib>
  12. #include <string>
  13. #include <list>
  14. #include <bitset>
  15. #include <iomanip>
  16. #include <cmath>
  17. #include <sstream>
  18. #include <deque>
  19. #include <climits>
  20. #include <cassert>
  21.  
  22. using namespace std;
  23.  
  24. #define ull unsigned long long
  25. #define ll long long
  26. #define Max(x,y) ((x)>(y)?(x):(y))
  27. #define Min(x,y) ((x)<(y)?(x):(y))
  28. #define Sl(x) scanf("%lld",&x)
  29. #define Su(x) scanf("%llu",&x)
  30. #define S(x) scanf("%d",&x)
  31. #define IS(x) cin>>x
  32. #define ISF(x) getline(cin,x)
  33. #define pii pair<int,int>
  34. #define pll pair<ll,ll>
  35. #define pps pair<ll,pll>
  36. #define ppf pair<pll,ll>
  37. #define psi pair<string,int>
  38. #define pis pair<int,string>
  39. #define fr first
  40. #define se second
  41. #define MOD 1000000007
  42. #define MP(x,y) make_pair(x,y)
  43. #define eps 1e-7
  44. #define V(x) vector<x>
  45. #define pb(x) push_back(x)
  46. #define mem(x,i) memset(x,i,sizeof(x))
  47. #define fori(i,s,n) for(i=(s);i<(n);i++)
  48. #define ford(i,s,n) for(i=(n);i>=(s);--i)
  49. #define INF 8944674407370955161LL
  50. #define debug(i,st,arr) fori(i,0,st){cout<<arr[i]<<" ";}cout<<endl;
  51. #define forci(i,sw) for((i)=(sw).begin();(i)!=(sw).end();(i)++)
  52. #define forcd(i,sw) for((i)=(sw).rbegin();(i)!=(sw).rend();(i)++)
  53.  
  54. int abs(int x) {if(x < 0) return -x; return x;}
  55.  
  56. map<pii, int> m1;
  57. char a[101][101];
  58. int vis[101][101];
  59. int path[15][15];
  60. int sx, sy, n, m, sk, fk;
  61. bool f[15];
  62. int ans;
  63. void func (int nw, int k, int n, int curr) {
  64. if (n == k) {
  65. if (curr + path[nw][fk] < ans) {
  66. ans = path[nw][fk] + curr;
  67. }
  68. return;
  69. }
  70.  
  71. for (int i = 0; i < k + 1; i++) {
  72. if (i != fk && !f[i]) {
  73. f[i] = true;
  74. func (i, k, n + 1, curr + path[nw][i]);
  75. f[i] = false;
  76. }
  77. }
  78. }
  79.  
  80.  
  81. bool check(int x, int y)
  82. {
  83. if(vis[x][y] != 0 || x < 0 || y < 0 || x >= n || y >= m || a[x][y] == '#')
  84. return false;
  85. return true;
  86. }
  87.  
  88. void bfs()
  89. {
  90. queue<pair<int, int> > q;
  91. q.push(pii(sx, sy));
  92. int c = 0;
  93. while (!q.empty()) {
  94. pii pr = q.front();
  95. q.pop();
  96.  
  97. if(check(pr.fr + 1, pr.se)) {
  98. q.push(pii(pr.fr+1, pr.se));
  99. vis[pr.fr+1][pr.se] = vis[pr.fr][pr.se]+1;
  100. }
  101.  
  102. if(check(pr.fr - 1, pr.se)) {
  103. q.push(pii(pr.fr-1, pr.se));
  104. vis[pr.fr-1][pr.se] = vis[pr.fr][pr.se]+1;
  105. }
  106.  
  107. if(check(pr.fr, pr.se + 1)) {
  108. q.push(pii(pr.fr, pr.se+1));
  109. vis[pr.fr][pr.se+1] = vis[pr.fr][pr.se]+1;
  110. }
  111.  
  112. if(check(pr.fr, pr.se-1)) {
  113. q.push(pii(pr.fr, pr.se-1));
  114. vis[pr.fr][pr.se-1] = vis[pr.fr][pr.se]+1;
  115. }
  116. }
  117. for (map<pii, int>::iterator it = m1.begin(); it != m1.end(); it++) {
  118. path[m1[pii(sx, sy)]][it->second] = path[it->second][m1[pii(sx, sy)]] = vis[it->first.first][it->first.second] - 1;
  119. }
  120. }
  121. int main()
  122. {
  123. int t, k;
  124.  
  125. cin >> t;
  126. while (t--) {
  127. cin >> n >> m;
  128. k = 0;
  129. m1.clear();
  130. for (int i = 0; i < 15; i++) {
  131. for (int j = 0; j < 15; j++) {
  132. path[i][j] = 99999999;
  133. }
  134. }
  135. for (int i = 0; i < n; i++) {
  136. scanf("%s", a[i]);
  137. for (int j = 0; j < m; j++) {
  138. if (a[i][j] == 'W' || a[i][j] == 'T' || a[i][j] == 'C') {
  139. m1[pii(i, j)] = k++;
  140. //cout << i << " " << j << " " << k - 1 <<endl;
  141. }
  142. if (a[i][j] == 'T') {
  143. sk = k-1;
  144. }
  145. if (a[i][j] == 'W') {
  146. fk = k-1;
  147. }
  148. }
  149. }
  150.  
  151. for (map<pii, int>::iterator it = m1.begin(); it != m1.end(); it++) {
  152.  
  153. for (int i = 0; i < n; i++) {
  154. for (int j = 0; j < m; j++) vis[i][j] = 0;
  155. }
  156. sx = it->first.first;
  157. sy = it->first.second;
  158. vis[sx][sy] = 1;
  159. bfs();
  160.  
  161. }
  162. bool f1 = false;
  163. for (int i = 0; i < k; i++) {
  164. for (int j = 0; j < i; j++) {
  165. if (path[i][j] == -1) {
  166. f1 = true;
  167. break;
  168. }
  169. }
  170. if(f1) break;
  171. }
  172. if (f1) {
  173. cout << "Mission Failed!\n";
  174. continue;
  175. } else {
  176. if (k == 2) {
  177. cout << path[fk][sk] << endl;
  178. } else {
  179. memset(f, 0, sizeof(f));
  180. ans = 99999999;
  181. f[fk] = f[sk] = true;
  182. for (int i = 0; i < k; i++) {
  183. if(i != sk && i != fk) {
  184. func(i, k - 1, 1, path[sk][i]);
  185. }
  186. }
  187. cout << ans << endl;
  188. }
  189.  
  190.  
  191. }
  192. }
  193.  
  194.  
  195. return 0;
  196. }
  197.  
  198.  
  199.  
  200.  
Time limit exceeded #stdin #stdout 5s 3532KB
stdin
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
stdout
8
396
396