yukicoder No.460 裏表ちわーわ

問題URL : http://yukicoder.me/problems/no/460

問題概要

各マスが黒か白からなるm x nの盤面が与えられる．
白と黒は表裏になっている．
操作としてあるマスとその8近傍のマス（端の場合はマスが存在する箇所だけ）をひっくり返すことができる．
すべてのマスを白にすることができるならば，最小操作回数を求めよ．
不可能な場合はImpossibleと表示せよ．

解法

盤面の一番上の行と一番左の列は合計m+n-1マスある．
これらのマスで操作を行うかを全探索する．
以下，それ以外のマスについてのみ操作を行う場合を考える．
上からi行目(0-indexed)，左からj列目(0-indexed)のマスを(i,j)(0-indexed)とすると，
(1,1)で操作を行わなければならないのは(0,0)が黒である場合のみである．
なぜなら，(0,0)をひっくり返せる操作は(1,1)での操作のみだからである．
あとはこれを順番に繰り返せばよい．
(0,0), (0,1), (0,2), ..., (0,n-1), (1,0), ... といった順番でマスを見ていき，(i,j)が黒であったらその右下のマス(i+1,j+1)で操作を行う．
(m-1, n)までマスを見終わったとき，盤面が全て白になっている場合の操作回数の最小値が求める答えとなる．
計算量はO(2^(m+n)*m*n)時間

コード

vvint vv;
int h, w;

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()) {
    v.assign(a, vector<T>(b, t));
}

bool inside(int y, int x) {
    return 0 <= y && y < h && 0 <= x && x < w;
}

void change(int y, int x, vvint &vv) {
    rep(i, 3) {
        rep(j, 3) {
            if(inside(y - 1 + i, x - 1 + j)) {
                vv[y - 1 + i][x - 1 + j] ^= 1;
            }
        }
    }
}

int check() {
    int ret = 0;
    vvint tmp = vv;
    rep(i, h) {
        rep(j, w) {
            if(tmp[i][j]) {
                if(!inside(i + 1, j + 1)) return INF;
                ret++;
                change(i + 1, j + 1, tmp);
            }
        }
    }
    return ret;
}


int dfs(int y, int x) {
    if(x == w) return dfs(1, 0);
    if(y == h) return check();

    int ret = INF;
    if(y == 0) {
        mins(ret, dfs(y, x + 1));
        change(0, x, vv);
        mins(ret, dfs(y, x + 1) + 1);
        change(0, x, vv);
    }
    else {
        mins(ret, dfs(y + 1, x));
        change(y, 0, vv);
        mins(ret, dfs(y + 1, x) + 1);
        change(y, 0, vv);
    }
    return ret;
}


void mainmain() {
    cin >> h >> w;
    initvv(vv, h, w);
    rep(i, h) rep(j, w) cin >> vv[i][j];
    int ans = dfs(0, 0);
    cout << (ans >= INF / 2 ? "Impossible" : to_string(ans)) << endl;
}

コメント

SRMで似た問題を解いた気がするけど思ったより時間がかかってしまった．