Submission #162413

---

Source Code Expand

#include <iostream>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> P;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

int main() {
    int r, c, sy, sx, gy, gx;
    int count = 0;
    char maze[50][50];
    bool has_arrived[50][50];
    queue<P> q;
    cin >> r >> c >> sy >> sx >> gy >> gx;
    for (int y=0; y<r; y++) {
        for (int x=0; x<c; x++) {
            cin >> maze[x][y];
            has_arrived[x][y] = false;
        }
    }
    q.push(P(sx-1, sy-1));
    q.push(P(-1, -1));
    has_arrived[sx][sy] = true;
    while (q.size() > 1) {
        P pos = q.front();
        q.pop();
        if (pos.first < 0) {
            count++;
            q.push(P(-1, -1));
            continue;
        }
        for (int i=0; i<4; i++) {
            int nx = pos.first+dx[i];
            int ny = pos.second+dy[i];
            if (nx < 0 || c <= nx || ny < 0 || r <= ny) {
                continue;
            }
            if (!has_arrived[nx][ny] && maze[nx][ny] == '.') {
                q.push(P(nx, ny));
                has_arrived[nx][ny] = true;
            }
        }
        if (pos.first == gx-1 && pos.second == gy-1) {
            cout << count << endl;
            return 0;
        }
    }
    return 1;
}

Submission Info

Judge Result