KUPC2012 H : 植林

問題概要

H*W(H,W<1000, H,W:even)の盤面で変則ライツアウトを行う。ルールは選んだマスの同じ行、列をフリップする。最小手数の盤面を出力する。

解法

よく理解できていない…。各マスについて、自マスを含む同じ行、列についてxorをとったものを反転したものが答えになっている。パリティ符号みたいなもの？

acceptされたコード

#include <cstdio>
using namespace std;

const int MAX_N = 1000;

int H, W;
int ys[MAX_N], xs[MAX_N];
int orig[MAX_N][MAX_N];
int ans[MAX_N][MAX_N];
void init() {
	scanf("%d%d", &H, &W);
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			scanf("%d", orig[i] + j);
			ys[i] ^= orig[i][j];
			xs[j] ^= orig[i][j];
		}
	}

}

void solve() {
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			printf("%d%c", 1 ^ orig[i][j] ^ ys[i] ^ xs[j], j == W-1 ? '\n': ' ');
		}
	}
}

int main() {
	init();
	solve();

	return 0;
}