Submission #1707350

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Point {
    int x;
    int y;
    bool operator==(const Point& pos) { return x==pos.x && y==pos.y; }
    bool operator!=(const Point& pos) { return x!=pos.x || y!=pos.y; }
};
vector<vector<int>> map;
int height, width;
bool can_move_on(Point pos){ 
    return pos.x>=0    && pos.y>=0 
        && pos.x<width && pos.y<height 
        && map[pos.y][pos.x] == -1; 
}
void input(){
    char tmp;
    for(auto &y: map)
        for(auto &x: y){
            cin >> tmp;        
            x = tmp=='.' ? -1 : -100;
        }
}
int main() {
    cin >> height >> width;

    Point start, goal;
    cin >> start.y >> start.x;
    start.x -= 1; start.y -= 1;
    cin >> goal.y >> goal.x;
    goal.x -= 1; goal.y -= 1;

    map.resize(height);
    for(auto &x: map) x.resize(width);
    input();

    queue<Point> que;
    que.push(start);
    map[start.y][start.x] = 0;
    while(!que.empty()){
        Point now = que.front(); que.pop();
        int step = map[now.y][now.x];
        if(now == goal) { cout << step << endl; return 0; } // Goal
        vector<int> next_x = {-1, 0, 1, 0};
        vector<int> next_y = {0 ,-1, 0, 1};
        for(int i=0; i<4; i++) {
            Point next = {now.x+next_x[i], now.y+next_y[i]};
            if(can_move_on(next)){
                map[next.y][next.x] = step+1;
                que.push(next);
            }
        }
    }
    cout << -1 << endl;
}

Submission Info

Judge Result