Advertisement
georgiy110802

Untitled

Jan 31st, 2022
849
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.54 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Point
  6. {
  7.     int i, j;
  8. };
  9.  
  10. int n, m;
  11. const int INF = (int)1e9;
  12.  
  13. bool can(Point p)
  14. {
  15.     return 0 <= p.i && 0 <= p.j && p.i < n && p.j < m;
  16. }
  17.  
  18. main()
  19. {
  20.     ios::sync_with_stdio(0);
  21.     cin.tie(0);
  22.     cin >> n >> m;
  23.     vector<vector<bool>> p(n, vector<bool>(m));
  24.     Point start, finish;
  25.     for(int i = 0; i < n; i++)
  26.     {
  27.         string s;
  28.         cin >> s;
  29.         for(int j = 0; j < m; j++)
  30.         {
  31.             if(s[j] == 'S')
  32.                 start = {i, j}, p[i][j] = true;
  33.             if(s[j] == 'F')
  34.                 finish = {i, j}, p[i][j] = true;
  35.             if(s[j] == '.')
  36.                 p[i][j] = true;
  37.         }
  38.     }
  39.     queue<Point> q;
  40.     q.push(start);
  41.     vector<vector<int>> dp(n, vector<int>(m, INF));
  42.     vector<vector<bool>> vis(n, vector<bool> (m, false));
  43.     dp[start.i][start.j] = 0;
  44.     while(!q.empty())
  45.     {
  46.         Point cur = q.front();
  47.         q.pop();
  48.         vis[cur.i][cur.j] = true;
  49.         for(int i = 1; ; i++)
  50.         {
  51.             Point next = {cur.i + i, cur.j};
  52.             if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
  53.             {
  54.                 dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
  55.                 q.push(next);
  56.             }
  57.             else
  58.                 break;
  59.         }
  60.         for(int i = -1; ; i--)
  61.         {
  62.             Point next = {cur.i + i, cur.j};
  63.             if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
  64.             {
  65.                 dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
  66.                 q.push(next);
  67.             }
  68.             else
  69.                 break;
  70.         }
  71.         for(int j = 1; ; j++)
  72.         {
  73.             Point next = {cur.i, cur.j + j};
  74.             if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
  75.             {
  76.                 dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
  77.                 q.push(next);
  78.             }
  79.             else
  80.                 break;
  81.         }
  82.         for(int j = -1; ; j--)
  83.         {
  84.             Point next = {cur.i, cur.j + j};
  85.             if(can(next) && p[next.i][next.j] && !vis[next.i][next.j] && dp[next.i][next.j] == INF)
  86.             {
  87.  
  88.                 dp[next.i][next.j] = dp[cur.i][cur.j] + 1,
  89.                 q.push(next);
  90.             }
  91.             else
  92.                 break;
  93.         }
  94.     }
  95.     if(dp[finish.i][finish.j] == INF)
  96.         cout << -1;
  97.     else
  98.         cout << dp[finish.i][finish.j];
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement