ABC088: 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"; }