結果

問題 No.460 裏表ちわーわ
ユーザー hirakich1048576hirakich1048576
提出日時 2016-05-25 16:22:33
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 2,488 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 23,552 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-05-06 18:01:52
合計ジャッジ時間 1,704 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 4 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 17 ms
6,940 KB
testcase_06 AC 17 ms
6,944 KB
testcase_07 AC 33 ms
6,940 KB
testcase_08 AC 37 ms
6,944 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 37 ms
6,940 KB
testcase_11 AC 17 ms
6,944 KB
testcase_12 AC 28 ms
6,940 KB
testcase_13 AC 40 ms
6,944 KB
testcase_14 AC 40 ms
6,940 KB
testcase_15 AC 41 ms
6,940 KB
testcase_16 AC 17 ms
6,944 KB
testcase_17 AC 40 ms
6,944 KB
testcase_18 AC 41 ms
6,940 KB
testcase_19 AC 40 ms
6,944 KB
testcase_20 AC 17 ms
6,944 KB
testcase_21 AC 39 ms
6,944 KB
testcase_22 AC 40 ms
6,940 KB
testcase_23 AC 39 ms
6,944 KB
testcase_24 AC 42 ms
6,944 KB
testcase_25 AC 0 ms
6,944 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:175:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  175 |         scanf("%d %d", &m, &n);
      |         ^~~~~~~~~~~~~~~~~~~~~~
main.c:179:25: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  179 |                         scanf("%d", &x);
      |                         ^~~~~~~~~~~~~~~

ソースコード

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