ABC 088 D - Grid Repainting
問題
コード
typedef pair<int,int> pii; int main(){ //cout.precision(10); cin.tie(0); ios::sync_with_stdio(false); int H,W; cin >> H >> W; char s[100][100]; vector<vector<int>> dist(H,vector<int>(W,-1)); int ct = 0; rep(i,H)rep(j,W){ cin >> s[i][j]; if(s[i][j] == '.')ct++; } queue<pii> q; dist[0][0] = 1; q.push(pii(0,0)); while(!q.empty()){ pii r = q.front(); q.pop(); if(r.first < H-1 && dist[r.first+1][r.second] == -1 && s[r.first+1][r.second] == '.'){ dist[r.first+1][r.second] = dist[r.first][r.second] + 1; q.push(pii(r.first+1,r.second)); } if(r.second < W-1 && dist[r.first][r.second+1] == -1 && s[r.first][r.second+1] == '.'){ dist[r.first][r.second+1] = dist[r.first][r.second] + 1; q.push(pii(r.first,r.second+1)); } if(r.first > 0 && dist[r.first - 1][r.second] == -1 && s[r.first-1][r.second] == '.'){ dist[r.first-1][r.second] = dist[r.first][r.second] + 1; q.push(pii(r.first-1,r.second)); } if(r.second > 0 && dist[r.first][r.second-1] == -1 && s[r.first][r.second-1] == '.'){ dist[r.first][r.second-1] = dist[r.first][r.second] + 1; q.push(pii(r.first,r.second-1)); } } if(dist[H-1][W-1] == -1) cout << -1 << endl; else cout << ct - dist[H-1][W-1] << endl; }
解法
bfsで最小コストを求め全体の白の個数から引く