Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #define x first
- #define y second
- #define pb push_back
- using namespace std;
- const int dx[4] = {-1,0,1,0};
- const int dy[4] = {0,1,0,-1};
- int n,m;
- const int INF = 1000000000;
- bool is_correct(int x,int y){
- return x >= 0 && x < n && y >= 0 && y < m;
- }
- int main()
- {
- cin >> n >> m;
- vector<vector<int>> g(n,vector<int> (m));
- vector<vector<bool>> used(n,vector<bool>(m));
- vector <vector<int>> dist(n,vector<int> (m,INF));
- dist[0][0] = 0;
- used[0][0] = true;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++){
- cin >> g[i][j];
- if (g[i][j] == 1)
- used[i][j] = 1;
- }
- queue<pair<int,int>> q;
- q.push({0,0});
- while (!q.empty()){
- auto p = q.front();
- q.pop();
- for (int i = 0; i < 4; i++){
- int x = p.x + dx[i];
- int y = p.x + dy[i];
- while (is_correct(x,y) && g[x][y] == 0){
- x += dx[i];
- y += dy[i];
- }
- if (!is_correct(x,y)){
- x -= dx[i];
- y -= dy[i];
- }
- if (g[x][y] == 2){
- cout << dist[p.x][p.y] + 1 << endl;
- return 0;
- }
- if (!used[x][y]){
- q.push({x,y});
- used[x][y] = true;
- dist[x][y] = dist[p.x][p.y] + 1;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement