fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. #define task ""
  7. #define fi first
  8. #define se second
  9. #define maxinp (int)(1500)
  10. #define MODUL (int)(1e9+57)
  11. #define siz(x) (int)(x.size())
  12. #define len(x) (int)(x.length())
  13. #define whole(x) x.begin(), x.end()
  14. #define FOR(i, x, y) for(int i=x; i<=y; ++i)
  15. #define FORl(i, x, y) for(int i=x; i<y; ++i)
  16. #define FORb(i, x, y) for(int i=x; i>=y; --i)
  17. #define FORlb(i, x, y) for(int i=x; i>y; --i)
  18. #define MEMS(x, val) memset(x, val, sizeof(x))
  19. #define FILEOP(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
  20. typedef unsigned long long ull;
  21. typedef pair<int, int> ii;
  22. typedef vector<int> vi;
  23. typedef queue<ii> qii;
  24. typedef long long ll;
  25. int nextx[4] = {-1, 0, 0, 1};
  26. int nexty[4] = {0, -1, 1, 0};
  27. bool Free[maxinp][maxinp];
  28. int Time[maxinp][maxinp];
  29. char a[maxinp][maxinp];
  30. int m, n, res, nTime;
  31. qii mainq, subq;
  32. ii start[3];
  33. int nInstruction = 0;
  34. void Debug()
  35. {
  36.  
  37. cout << endl;
  38. FOR(i, 1, m)
  39. {
  40. FOR(j, 1, n)
  41. {
  42. cout << Time[i][j] << " ";
  43. }
  44. cout << endl;
  45. }
  46. cout << endl;
  47.  
  48.  
  49. }
  50.  
  51.  
  52. void Enter()
  53. {
  54. int cnt = 1;
  55. MEMS(Free, true);
  56.  
  57.  
  58. scanf("%d%d", &m, &n);
  59.  
  60.  
  61.  
  62.  
  63. FOR(i, 1, m)
  64. {
  65. FOR(j, 1, n)
  66. {
  67.  
  68. cin >> a[i][j];
  69.  
  70.  
  71. if(a[i][j] != 'X')
  72. {
  73. Time[i][j] = 0;
  74.  
  75. mainq.push(ii(i, j));
  76.  
  77. if(a[i][j] == 'L')
  78. {
  79. start[cnt] = ii(i, j);
  80. ++cnt;
  81. }
  82.  
  83. Free[i][j] = false;
  84. }
  85. else Time[i][j] = 1234567890;
  86.  
  87. ++nInstruction;
  88.  
  89.  
  90. }
  91. }
  92.  
  93. }
  94.  
  95. //Check
  96. bool IsValid(int _x, int _y)
  97. {
  98. return(_x >= 1 && _y >= 1 && _x <= m && _y <= n && Free[_x][_y]);
  99. }
  100.  
  101. void PreProcess()
  102. {
  103. while(!mainq.empty())
  104. {
  105. int curx = mainq.front().first;
  106. int cury = mainq.front().second;
  107.  
  108. ++nInstruction;
  109. mainq.pop();
  110.  
  111. FOR(i, 0, 3)
  112. {
  113. int x = curx + nextx[i];
  114. int y = cury + nexty[i];
  115.  
  116. if(IsValid(x, y))
  117. {
  118. if(a[x][y] == 'X')
  119. {
  120. Free[x][y] = false;
  121. mainq.push(ii(x, y));
  122. Time[x][y] = min(Time[x][y], Time[curx][cury] + 1);
  123. }
  124. }
  125. }
  126.  
  127. }
  128.  
  129. //Debug();
  130.  
  131.  
  132.  
  133. }
  134. void FloodFill1(ii st1, ii st2)
  135. {
  136. mainq.push(st1);
  137. Free[st1.first][st1.second] = false;
  138. while(!mainq.empty())
  139. {
  140. int curx = mainq.front().first;
  141. int cury = mainq.front().second;
  142.  
  143. //Time[curx][cury] = nTime;
  144. ++nInstruction;
  145.  
  146. mainq.pop();
  147.  
  148. FOR(i, 0, 3)
  149. {
  150. int x = curx + nextx[i];
  151. int y = cury + nexty[i];
  152. ii dir = ii(x, y);
  153.  
  154. if(IsValid(x, y))
  155. {
  156. Free[x][y] = false;
  157. if(dir == st2) return;
  158. if(Time[x][y] <= res) mainq.push(dir);
  159. else subq.push(dir);
  160. }
  161. }
  162.  
  163. if(mainq.empty())
  164. {
  165. ++res;
  166. swap(mainq, subq);
  167. }
  168.  
  169. }
  170. }
  171.  
  172. //Process
  173. void Solve()
  174. {
  175. res = 0;
  176. PreProcess();
  177. MEMS(Free, true);
  178. FloodFill1(start[1], start[2]);
  179. printf("%d", res);
  180.  
  181.  
  182. cerr << endl;
  183. cerr << nInstruction << endl;
  184.  
  185. }
  186.  
  187. //Main Procedure
  188. int main()
  189. {
  190. Enter();
  191. Solve();
  192. return 0;
  193. }
Success #stdin #stdout #stderr 0s 29256KB
stdin
Standard input is empty
stdout
1
stderr
1