ABC088: D - Grid Repainting

問題

D - Grid Repainting

解説

白いマスの数から初めのマスを含めた最短経路長を引けば良い。

最短経路が求まらない場合は-1と出力する。

int constexpr INF = 1L<<29;

constexpr bool in_range(int y, int x, int H, int W) {
    return 0 <= x && x < W && 0 <= y && y < H;
}

int bfs(vector<string> const& g) {
    const int H = g.size(), W = g[0].size();
    queue<pair<int, int>> q;
    vector<vector<int>> dist(H, vector<int>(W, INF));
    dist[0][0] = 0;
    q.emplace(0, 0);
    while(!q.empty()) {
        auto p = q.front(); q.pop();
        int y = p.first, x = p.second;
        int constexpr dy[] = {0,-1,0,+1};
        int constexpr dx[] = {-1,0,+1,0};
        rep(k, 4) {
            int ny = y + dy[k], nx = x + dx[k];
            if (!in_range(ny, nx, H, W)) continue;
            if (g[ny][nx] == '#') continue;
            if (dist[ny][nx] < INF) continue;
            dist[ny][nx] = dist[y][x] + 1;
            q.emplace(ny, nx);
        }
    }
    return dist[H - 1][W - 1];
}

int main() {
    int H, W; cin >> H >> W;
    vector<string> g;
    rep(i, H) {
        string s; cin >> s;
        g.push_back(s);
    }
    int shiro = 0;
    rep(i, H) rep(j, W) {
        shiro += g[i][j] == '.';
    }
    auto min_dist = bfs(g);
    if (min_dist == INF) {
        cout << -1 << "\n";
        return 0;
    }
    cout << shiro - min_dist - 1 << "\n";
}