3828591_ac_47ms_416k.cpp

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

#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int height, width;
int size;

class Puzzle
{
private:
	string str[25];
public:
	int a, b, c, d;
	void show(int k)
	{
		cout << str[k];
	}

	Puzzle(int foo)
	{
		int i;
		string tmp;
		
		getline(cin, tmp);
		for(i = 0; i < height; i++)
		{
			getline(cin, str[i]);
		}
		cin >> a >> b >> c >> d;
		getline(cin, tmp);
	}
	Puzzle() : a (0), b (0), c (0), d (0) {}
};

Puzzle puzzle[101];
int pos[11][11];
int succ;
int used[101];

void dfs(int num)
{
	if (succ)
		return ;
	int i;
	if (num == size * size)
	{
		succ = 1;
		return ;
	}
	int x = num / size + 1;
	int y = num % size + 1;
	int c, d;
	c = puzzle[pos[x - 1][y]].c;
	d = puzzle[pos[x][y - 1]].d;
	for (i = 1; !succ && i <= size * size; i++)
	{
		if (!used[i] && puzzle[i].b + d == 0 && puzzle[i].a + c == 0)
		{
			pos[x][y] = i;
			used[i] = 1;
			dfs(num + 1);
			used[i] = 0;
		}
	}
}

int main()
{
	int i, j, k;

	cin >> size >> height >> width;
	for (i = 1; i <= size * size; i++)
	{
		puzzle[i] = Puzzle(i);
	}
	memset(pos, 0, sizeof(pos));
	memset(used, 0, sizeof(used));
	dfs(succ = 0);
	for (i = 1; i <= size; i++)
	{
		for (k = 0; k < height; k++)
		{
			for (j = 1; j <= size; j++)
			{
				puzzle[pos[i][j]].show(k);
			}
			cout << endl;
		}
	}
	return 0;
}