Submission #2674064

---

Source Code Expand

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
using P = pair<int, int>;

const int INF = (int)1e8;
int R, C;
int sx, sy, gx, gy;
char c[51][51];
int d[51][51];

int bfs(){
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    queue<P> que;
    que.push(P(sy, sx));
    d[sy][sx] = 0;

    while(not que.empty()){
        P p = que.front(); que.pop();
        int y = p.first, x = p.second;
        // cout << "(y, x) = " << y << ' ' << x << '\n';
        if(y == gy and x == gx) break;

        for(int i = 0; i < 4; i++){
            int ny = y + dy[i], nx = x + dx[i];
            // cout << "---(ny, nx) = " << ny << nx << '\n';
            if(0<=ny and ny<R and 0<=nx and nx<C and c[ny][nx]=='.' and d[ny][nx]==INF){
                // cout << "reachable" << '\n';
                d[ny][nx] = d[y][x] + 1;
                que.push(P(ny, nx));
            }
        }
    }

    return d[gy][gx];
}

int main(void){
    cin >> R >> C;
    cin >> sy >> sx; sy--; sx--;
    cin >> gy >> gx; gy--; gx--;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> c[i][j];
            d[i][j] = INF;
        }
    }

    cout << bfs() << '\n';
    return 0;
}

Submission Info

Judge Result