PuzzleCalculator.cpp

// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>


using namespace std;
/*
7种形状
00  0000  0     0 00    00   0
00        000 000  00  00   000
*/

int map[10][10];	//游戏网格
int inp[20];			//物块列表
bool isSolved;		//问题是否找到了解
int sum;		//总物块数
int m, n;	//m:行  n:列

//输出结果
void printAns() {
	//cout << "答案为" << endl;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

bool put(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int mark) {
	if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0 || x3 < 0 || y3 < 0 || x4 < 0 || y4 < 0 ||
		x1 >= m || y1 >= n || x2 >= m || y2 >= n || x3 >= m || y3 >= n || x4 >= m || y4 >= n)
		return false;
	if (mark && (map[x1][y1] || map[x2][y2] || map[x3][y3] || map[x4][y4]))return false;
	map[x1][y1] = map[x2][y2] = map[x3][y3] = map[x4][y4] = mark;
	return true;
}

int X[7][4][8] =
{
	//方形
	{
		{0,0,1,0,0,1,1,1},
		{-100,0,1,0,0,1,1,1},
		{-100,0,1,0,0,1,1,1},
		{-100,0,1,0,0,1,1,1}
	},
	//长条
	{
		{0,0,1,0,2,0,3,0},
		{0,0,0,1,0,2,0,3},
		{-100,0,0,0,0,0,0,0},
		{-100,0,0,0,0,0,0,0}
	},
	//反L
	{
		{0,0,0,1,0,2,1,2},
		{ 1,0,1,1,1,2,0,0 },
		{ 0,0,0,1,1,0,2,0 },
		{ 0,1,1,1,2,1,2,0 }
	},
	//正L
	{
		{ 0,2,1,0,1,1,1,2 },
		{ 0,0,0,1,0,2,1,0 },
		{ 0,0,1,0,2,0,2,1 },
		{ 0,0,0,1,1,1,2,1 }
	},
	//正Z
	{
		{ 0,0,0,1,1,1,1,2 },
		{ 0,1,1,0,1,1,2,0 },
		{ -100,0,1,0,2,0,2,1 },
		{ -100,0,0,1,1,1,2,1 }
	},
	//反Z
	{
		{ 0,0,1,0,1,1,2,1 },
		{ 0,1,0,2,1,0,1,1 },
		{ -100,0,1,0,2,0,2,1 },
		{ -100,0,0,1,1,1,2,1 }
	},
	//⊥
	{
		{ 0,1,1,0,1,1,1,2 },
		{ 0,0,0,1,0,2,1,1 },
		{ 0,0,1,0,2,0,1,1 },
		{ 1,0,0,1,1,1,2,1 }
	},

};

int dfs(int cnt) {
	//printAns();
	if (cnt == sum + 1) {
		printAns();
		return 1;
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int dir = 0; dir < 4; dir++) {
				int* p = X[inp[cnt - 1]][dir];
				if (put(i + p[0], j + p[1], i + p[2], j + p[3], i + p[4], j + p[5], i + p[6], j + p[7], cnt)) {
					if (dfs(cnt + 1))return 1;
					put(i + p[0], j + p[1], i + p[2], j + p[3], i + p[4], j + p[5], i + p[6], j + p[7], 0);
				}
			}
		}
	}
	return 0;
}

int main()
{
	memset(map, 0, sizeof map);
	cout << "问题是几行几列的？" << endl;
	cin >> m >> n;
	//debug1();
	sum = m * n >> 2;
	cout << "根据形状编号依次输入方块数据：方块0 长条1 反L2 正L3 正Z4 反Z5 ⊥6" << endl;
	for (auto i = 0; i < sum; i++)
		cin >> inp[i];
	dfs(1);
	cin >> m;
	return 0;
}

/**
6 4
1 0 6 6 2 4

6 4
0 4 2 1 6 6

超时，不可解↓
8 6
0 0 5 5 4 4 2 3 6 6 6 6

6 6
0 0 1 2 3 6 6 6 6
**/


// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件