Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int INF = (int)1e9;
- vector<vector<int>> p;
- struct Point
- {
- int i, j;
- };
- Point getPos(Point a, int ri, int rj)
- {
- int x = a.i, y = a.j;
- while(p[x + ri][y + rj] != 1 && p[x + ri][y + rj] != 2)
- {
- x += ri;
- y += rj;
- }
- if(p[x + ri][y + rj] == 2)
- return {x + ri, y + rj};
- else
- return {x, y};
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int n, m;
- cin >> n >> m;
- p.resize(n + 2, vector<int> (m + 2, 1));
- vector<pair<int, int>> c{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= m; j++)
- cin >> p[i][j];
- vector<vector<int>> dp(n + 2, vector<int> (m + 2, INF));
- dp[1][1] = 0;
- queue<Point> q;
- q.push({1, 1});
- while(!q.empty())
- {
- Point cur = q.front();
- q.pop();
- for(auto j : c)
- {
- Point next = getPos(cur, j.first, j.second);
- if(dp[next.i][next.j] == INF)
- {
- dp[next.i][next.j] = dp[cur.i][cur.j] + 1;
- q.push(next);
- }
- }
- }
- int ans = INF;
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= m; j++)
- if(p[i][j] == 2)
- ans = min(ans, dp[i][j]);
- cout << ans;
- }
Advertisement
Advertisement