Advertisement
Guest User

Untitled

a guest
Jun 24th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define inf LONG_MAX
  5.  
  6. using namespace std;
  7.  
  8. struct two
  9. {
  10.     ll x, y;
  11. };
  12.  
  13. char board[1000][1000];
  14.  
  15. ll dst[1000][1000];
  16.  
  17. ll n, m, startX, startY, finishX, finishY;
  18.  
  19. bool can(ll a, ll b)
  20. {
  21.     return a < n && a >= 0 && b >= 0 && b < m;
  22. }
  23.  
  24. vector <two> tp;
  25.  
  26. int main()
  27. {
  28.     freopen("input.txt", "r", stdin);
  29.     freopen("output.txt", "w", stdout);
  30.  
  31.     cin >> n >> m;
  32.  
  33.     for (int i = 0; i < n; ++i)
  34.         for (int j = 0; j < m; ++j)
  35.         {
  36.             cin >> board[i][j];
  37.  
  38.             if (board[i][j] == 'T')
  39.                 tp.push_back({i, j});
  40.  
  41.             dst[i][j] = inf;
  42.         }
  43.  
  44.     cin >> startX >> startY >> finishX >> finishY;
  45.  
  46.     startX--;
  47.     startY--;
  48.  
  49.     finishX--;
  50.     finishY--;
  51.  
  52.     queue <two> q;
  53.  
  54.     dst[startX][startY] = 0;
  55.  
  56.     q.push({startX, startY});
  57.  
  58.     while (!q.empty())
  59.     {
  60.         two cur = q.front();
  61.  
  62.         q.pop();
  63.  
  64.         if (can(cur.x + 1, cur.y) && dst[cur.x][cur.y] + 1 < dst[cur.x + 1][cur.y])
  65.         {
  66.             q.push({cur.x + 1, cur.y});
  67.  
  68.             dst[cur.x + 1][cur.y] = dst[cur.x][cur.y] + 1;
  69.         }
  70.  
  71.         if (can(cur.x - 1, cur.y) && dst[cur.x][cur.y] + 1 < dst[cur.x - 1][cur.y])
  72.         {
  73.             q.push({cur.x - 1, cur.y});
  74.  
  75.             dst[cur.x - 1][cur.y] = dst[cur.x][cur.y] + 1;
  76.         }
  77.         //
  78.         if (can(cur.x, cur.y + 1) && dst[cur.x][cur.y] + 1 < dst[cur.x][cur.y + 1])
  79.         {
  80.             q.push({cur.x, cur.y + 1});
  81.  
  82.             dst[cur.x][cur.y + 1] = dst[cur.x][cur.y] + 1;
  83.         }
  84.  
  85.         if (can(cur.x, cur.y - 1) && dst[cur.x][cur.y] + 1 < dst[cur.x][cur.y - 1])
  86.         {
  87.             q.push({cur.x, cur.y - 1});
  88.  
  89.             dst[cur.x][cur.y - 1] = dst[cur.x][cur.y] + 1;
  90.         }
  91.  
  92.         if (board[cur.x][cur.y] == 'T')
  93.             for (auto c : tp)
  94.                 if (dst[cur.x][cur.y] < dst[c.x][c.y])
  95.                 {
  96.                     q.push(c);
  97.  
  98.                     dst[c.x][c.y] = dst[cur.x][cur.y];
  99.                 }
  100.  
  101.     }
  102.  
  103.     if (dst[finishX][finishY] == inf)
  104.         dst[finishX][finishY] = -1;
  105.  
  106.     cout << dst[finishX][finishY];
  107.  
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement