pku1681.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 81 行

#include <stdio.h>
#include <string.h>

int v[22][22], tv[22][22], d[22][22];
int N;
char s[30];
int F[5][2] = {0, 0, 0, 1, 0, -1, 1, 0, -1, 0};

int check(int x)
{
	int i, j, d;
	int cnt = 0;
	memcpy(tv, v, sizeof(v));
	for (i = 1; i <= N; i++)
	{
		j = 1;
		if (x & (1 << (i - 1)))
		{
			cnt++;
			tv[i][j] = !tv[i][j];
			tv[i + 1][j] = !tv[i + 1][j];
			tv[i][j + 1] = !tv[i][j + 1];
			tv[i - 1][j] = !tv[i - 1][j];
			tv[i][j - 1] = !tv[i][j - 1];
		}
	}

	for (j = 2; j <= N; j++)
	{
		for (i = 1; i <= N; i++)
		{
			if (!tv[i][j - 1])
			{
				cnt++;
				tv[i][j] = !tv[i][j];
				tv[i + 1][j] = !tv[i + 1][j];
				tv[i][j + 1] = !tv[i][j + 1];
				tv[i - 1][j] = !tv[i - 1][j];
				tv[i][j - 1] = !tv[i][j - 1];
			}
		}
	}
	for (i = 1; i <= N; i++)
	{
		if (!tv[i][N])
			return N * N + 1;
	}
	return cnt;
}

void Solve()
{
	int i, j, min, tmp;
	scanf("%d", &N);
	for (i = 1; i <= N; i++)
	{
		scanf("%s", s + 1);
		for (j = 1; j <= N; j++)
			v[i][j] = s[j] == 'y' ? 1 : 0;
	}
	min = N * N + 1;
	for (i = 0; i < (1 << N); i++)
	{
		tmp = check(i);
		if (tmp < min)
			min = tmp;
	}
	if (min == N * N + 1)
		printf("inf\n");
	else
		printf("%d\n", min);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
		Solve();
	return 0;
}