fork(2) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
1
https://ideone.com/nLrE1f
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!