AtCoder Regular Contest 040 C - Z塗り

問題

　 $N\times N(N \le 100)$ のマス目状になっている床を一色に塗ることを考える。一回の塗る操作で、ある整数 $r,c$ に対して「 $i=r$ かつ $j\le c$ 」または「 $i=r + 1$ かつ $j \ge c$ 」を満たすような全てのマス $(i, j)$ を塗ることができる。部分的に塗られている初期状態が与えられるので、全てのマスを塗る最小の操作回数を求めよ。

解法

　各行に対して右側からみてまだ塗られていないマスがあったらそこを $(r, c)$ として塗る貪欲法で計算量は $O(n^3)$ でありこの問題が解ける。

反省

　9分4秒(0WA)でAC。特に難しいところもなく。昨日一昨日に比べてこの難易度の差。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<string> S(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = N - 1; j >= 0; j--) {
            if (S[i][j] == '.') {
                //(i, j)で一回塗る
                ans++;

                //i段目が塗られる
                for (ll k = 0; k <= j; k++) {
                    S[i][k] = 'o';
                }

                //i + 1段目が塗られる
                if (i != N - 1) {
                    for (ll k = j; k < N; k++) {
                        S[i + 1][k] = 'o';
                    }
                }
            }
        }
    }

    cout << ans << endl;
}