結果

問題 No.460 裏表ちわーわ
ユーザー hirakich1048576
提出日時 2016-05-24 17:26:15
言語 C90
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 2,260 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 22,912 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-29 02:33:39
合計ジャッジ時間 1,779 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:161:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  161 |         scanf("%d %d", &m, &n);
      |         ^~~~~~~~~~~~~~~~~~~~~~
main.c:165:25: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  165 |                         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;
}

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 = (n - 1) * 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 = (n - 1) * 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;
	}

	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 = (n - 1) * 2; i >= 0; i--) *axes(where(i)) = false;

	for (;;) {
		if (fill()) {
			int maybe = howmany();
			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