pku1753.cpp

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

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

int m[16];
int dir[5][2] = {1, 0, -1, 0, 0, 1, 0, -1, 0, 0};
int min;

int In(int x, int y)
{
	return x >= 0 && x < 4 && y >= 0 && y < 4;
}

void init()
{
	int x, y, i, j, nx, ny;
	for (j = 0; j < 16; j++)
	{
		x = j / 4;
		y = j % 4;
		m[j] = 0;
		for (i = 0; i < 5; i++)
		{
			nx = x + dir[i][0];
			ny = y + dir[i][1];
			if (In(nx, ny))
			{
				m[j] += (1 << (nx * 4 + ny));
			}
		}
	}
}

void DFS(int val, int time, int k)
{
	if (val == 0 || val == (1 << 16) - 1)
	{
		if (time < min)
		{
			min = time;
		}
	}
	if (time >= min || k > 15)
	{
		return;
	}
	DFS(val, time, k + 1);
	DFS(val ^ m[k], time + 1, k + 1);
}
int main()
{
	int S = 0;
	char s[5];
	int i, j;
	init();
	for (i = 0; i < 4; i++)
	{
		scanf("%s", s);
		for (j = 0; j < 4; j++)
		{
			if (s[j] == 'b')
			{
				S += 1 << (i * 4 + j);
			}
		}
	}
	min = 170;
	DFS(S, 0, 0);
	if (min == 170)
	{
		printf("Impossible\n");
	}
	else
	{
		printf("%d\n", min);
	}
	return 0;
}