結果

問題 No.460 裏表ちわーわ
ユーザー hirakich1048576hirakich1048576
提出日時 2016-05-25 16:22:33
言語 C90
(gcc 12.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,488 bytes
コンパイル時間 1,890 ms
コンパイル使用メモリ 26,624 KB
最終ジャッジ日時 2025-01-08 00:41:53
合計ジャッジ時間 2,772 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.c:1:1: error: C++ style comments are not allowed in ISO C90
    1 | // C is for "Chiwawa"
      | ^
main.c:1:1: note: (this will be reported only once per input file)

ソースコード

diff # 

// C is for "Chiwawa"

#include <stdio.h>
#include <stdbool.h>

#define IMPO "Impossible"
#define N_MAX 8

#define INF 1145141919

#define CPARSE(a, b) ((a) * n + (b))
// #define AXES(a, x) 

int m, n;
bool a[N_MAX][N_MAX];

bool b[N_MAX][N_MAX];
bool c[N_MAX][N_MAX];

void deb(){
	int i, j;
	for(i=0;i<m;i++)for(j=0;j<n;j++)putchar(b[i][j]?'#':'_'),putchar(n-j-1?' ':'\n');
		return;
}

void dec(){
	int i, j;
	for(i=0;i<m;i++)for(j=0;j<n;j++)putchar(c[i][j]?'#':'_'),putchar(n-j-1?' ':'\n');
		return;
}

bool* axes(int x) {
	return (&b[(x) / n][(x) % n]);
}

int where(int a){
	return (a < n) ? CPARSE(0, a) : CPARSE(a+1-n, 0);
}

bool isexist(int i, int j){
	return (0 <= i) && (i < m) && (0 <= j) && (j < n);
}

void seija(int w){
	int i, j, k;
	int e[9][2] = {
		{-1, -1},
		{-1,  0},
		{-1, +1},
		{ 0, -1},
		{ 0,  0},
		{ 0, +1},
		{+1, -1},
		{+1,  0},
		{+1, +1}
	};
	
	i = w / n, j = w % n;

	for (k = 0; k < 9; k++) {
		int li, lj;
		li = i + e[k][0];
		lj = j + e[k][1];
		if (isexist(li, lj)) c[li][lj] ^= 1;
	}

	return;
}

bool incf(){
	bool* y;
	
	int i = m + n - 2;

	for (;;) {
		y = axes(where(i));
		if (!*y) {
			*y = true;
			return true;
		}
		*y = false;
		i--;
		if (i < 0)
			return false;
	}
}

bool fill(){
	int i, j;
	
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			c[i][j] = a[i][j];
		}
	}

	for (i = m + n - 2; i >= 0; i--) {
		if (*axes(where(i))) seija(where(i));
	}

	for (i = 1; i < m; i++) {
		for (j = 1; j < n; j++) {
			if (c[i - 1][j - 1]) {
				b[i][j] = true;
				seija(CPARSE(i, j));
			} else {
				b[i][j] = false;
			}
		}

		if (c[i - 1][n - 1]) {
			return false;
		}
	}

	for (j = 0; j < n; j++) {
		if (c[m - 1][j])
			return false;
	}

	// deb();

	return true;

}

int howmany(){
	int result = 0;
	int i, j;

	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (b[i][j]) result++;
		}
	}

	return result;
}

int solve(){
	int i, j;

	int ans = INF;

	for (i = m + n -2; i >= 0; i--) *axes(where(i)) = false;

	for (;;) {
		// deb();
		if (fill()) {
			int maybe = howmany();
			// puts("Answer: ");
			// deb();
			// putchar('\n');
			// dec();
			// putchar('\n');
			if (maybe < ans) ans = maybe;
		}
		if(!incf())
			break;
	}

	if (ans < INF) {
		printf("%d\n", ans);
	} else {
		puts(IMPO);
	}
	return! 114514;
}

int main(void){
	int i, j;

	int x;

	scanf("%d %d", &m, &n);
	
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			scanf("%d", &x);
			a[i][j] = (bool)x;
		}
	}

	solve();
	return 0;
}
0