3818342_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int p[5][4][4];
int size[5][2];
int ok;
int pos[4][4];

void cpy(int des[4][4], int sou[4][4])
{
	for (int a = 0; a < 4; a++)
	{
		for (int b = 0; b < 4; b++)
		{
			des[a][b] = sou[a][b];
		}
	}
}

void dfs(int u, int puzzle[4][4])
{
	int i, j, a, b, x, y;
	int tmp[4][4], tmpp[4][4];

	if (ok)
		return ;
	if (u == n)
	{
		for (i = 0; i < 4; i++)
		{
			for (j = 0; j < 4; j++)
			{
				if (puzzle[i][j] != 1)
					return ;
			}
		}
		ok = 1;
		return ;
	}
	for (i = 0; ! ok && i <= 4 - size[u][0]; i++)
	{
		for (j = 0; j <= 4 - size[u][1]; j++)
		{
			cpy(tmp, puzzle);
			cpy(tmpp, pos);
			int fail = 0;
			for (a = i, x = 0; !fail && a < i + size[u][0]; a++, x++)
			{
				for (b = j, y = 0; b < j + size[u][1]; b++, y++)
				{
					if (p[u][x][y] == 1)
					{
						pos[a][b] = u + 1;
					}
					puzzle[a][b] += p[u][x][y];
					if (puzzle[a][b] > 1)
					{
						fail = 1;
						break;
					}
				}
			}
			if (fail)
			{
				cpy(puzzle, tmp);
				cpy(pos, tmpp);
				continue;
			}
			dfs(u + 1, puzzle);
			if (ok)
				break;
			cpy(puzzle, tmp);
			cpy(pos, tmpp);
		}
	}
}

void solve()
{
	int puzzle[4][4];

	memset(puzzle, 0, sizeof(puzzle));
	ok = 0;
	dfs(0, puzzle);
	if (ok == 0)
	{
		puts("No solution possible\n");
		return ;
	}
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			printf("%d", pos[i][j]);
		}
		puts("");
	}
	puts("");
}

int main()
{
	int i, j, k;
	char str[4];

	while (scanf("%d", &n) == 1 && n != 0)
	{
		for (i = 0; i < n; i++)
		{
			scanf("%d%d", &size[i][0], &size[i][1]);
			for (j = 0; j < size[i][0]; j++)
			{
				scanf("%s", str);
				for (k = 0; k < size[i][1]; k++)
				{
					p[i][j][k] = str[k] - '0';
				}
			}
		}
		solve();
	}
	return 0;
}