ABC 088 D - Grid Repainting

問題

atcoder.jp

コード

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で最小コストを求め全体の白の個数から引く