SRM 544 div1 med: FlipGame

問題

TopCoder Statistics - Problem Statement

H*W の盤面があり, それぞれのセルには 0 か 1 が書かれている。これを以下の操作を繰り返すことでセルに書かれた数をすべて 0 にしたい。

操作：盤面の辺を通る経路で, 左上から右下まで最短経路で行く。最短経路の左側のセルをすべてフリップ(0 -> 1, 1 -> 0)する

最小で何回の操作で目的を達成できるか。

解法

貪欲法でいけます。

各ステップに, 上から順番にどこまでフリップするかを考えます。
フリップする行はなるべく少ないほうが良いので, 最も右端にある 1 のところまでフリップさせる, ということを繰り返せば良いです。

class FlipGame {
public:
    int minOperations(vector <string> board) {
        int H = board.size(), W = board[0].size();
        int ans = 0;
        while (1) {
            bool finish = true;
            for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
                if (board[i][j] == '1') finish = false;
            }
            if (finish) break;
            int nc = 0;
            for (int i = 0; i < H; i++) {
                // nc 以降に 1 がないか探す
                int cut = W;
                for (; cut > nc; cut--) {
                    if (board[i][cut-1] == '1') break;
                }
                // nc までフリップさせる
                nc = cut;
                for (int j = 0; j < nc; j++) board[i][j] = (board[i][j]=='0' ? '1' : '0');
            }
            ans++;
        }
        return ans;
    }
};