Advertisement
Georgiy1108

Untitled

Oct 2nd, 2023
881
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = (int)1e9;
  6.  
  7. vector<vector<int>> p;
  8.  
  9. struct Point
  10. {
  11.     int i, j;
  12. };
  13.  
  14. Point getPos(Point a, int ri, int rj)
  15. {
  16.     int x = a.i, y = a.j;
  17.     while(p[x + ri][y + rj] != 1 && p[x + ri][y + rj] != 2)
  18.     {
  19.         x += ri;
  20.         y += rj;
  21.     }
  22.     if(p[x + ri][y + rj] == 2)
  23.         return {x + ri, y + rj};    
  24.     else
  25.         return {x, y};
  26. }
  27.  
  28. int main()
  29. {
  30.     ios::sync_with_stdio(0);
  31.     cin.tie(0);
  32.     int n, m;
  33.     cin >> n >> m;
  34.     p.resize(n + 2, vector<int> (m + 2, 1));
  35.     vector<pair<int, int>> c{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
  36.     for(int i = 1; i <= n; i++)
  37.         for(int j = 1; j <= m; j++)
  38.             cin >> p[i][j];
  39.     vector<vector<int>> dp(n + 2, vector<int> (m + 2, INF));
  40.     dp[1][1] = 0;
  41.     queue<Point> q;
  42.     q.push({1, 1});
  43.     while(!q.empty())
  44.     {
  45.         Point cur = q.front();
  46.         q.pop();
  47.         for(auto j : c)
  48.         {
  49.             Point next = getPos(cur, j.first, j.second);
  50.             if(dp[next.i][next.j] == INF)
  51.             {
  52.                 dp[next.i][next.j] = dp[cur.i][cur.j] + 1;
  53.                 q.push(next);
  54.             }
  55.         }
  56.     }
  57.     int ans = INF;
  58.     for(int i = 1; i <= n; i++)
  59.         for(int j = 1; j <= m; j++)
  60.             if(p[i][j] == 2)
  61.                 ans = min(ans, dp[i][j]);
  62.     cout << ans;
  63. }
Advertisement
Comments
Add Comment
Please, Sign In to add comment
Advertisement