POJ 3279 Fliptile

解法

一番上の行のflipの仕方を決めると、flipの仕方は一意に決まるので、一番上の行のflipパターンを全て試す。
蟻本に載ってる問題です

ソースコード

int h, w, tile[22][22];
int work[22][22],  pos[22][22];
int f;
void flip(int x, int y)
{
    work[y][x] ^= 1;
    pos[y][x] = 1;
    rep(i, 4)
    {
	int tx = x + dx[i], ty = y + dy[i];
	if (valid(tx, ty, w, h))
	    work[ty][tx] ^= 1;
    }
}
int main()
{
    scanf("%d%d", &h, &w);
    rep(i, h) rep(j, w)
	scanf("%d", &tile[i][j]);

    int min_flip = 33333, res_pos[22][22];
    rep(s, bin(w))
    {
	CL(pos, 0);
	COPY(work, tile);
	f = 0;

	rep(x, w)
	    if (s >> x & 1)
		flip(x, 0);

	for (int y = 1; y < h; ++y)
	    rep(x, w)
		if (work[y - 1][x])
		    flip(x, y);

	bool ok = true;
	rep(y, h) rep(x, w)
	    ok &= !work[y][x];


	if (ok && f < min_flip)
	{
	    min_flip = f;
	    COPY(res_pos, pos);
	}
    }
    if (min_flip == 33333)
	puts("IMPOSSIBLE");
    else
    {
	rep(y, h) rep(x, w)
	    printf("%d%c", res_pos[y][x], x + 1 == w ? '\n' : ' ');
    }
}