PicturePuzzle-Calculator/PuzzleCalculator.cpp at main · SweetsTime/PicturePuzzle-Calculator · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// 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 文件