龍博士魔術金字塔（平面）DFS破解
用DFS直接試出答案，最底下有範例測資。
語言：C++
計算時從最左下角的點開始排，不斷換拼片或擺法直到成功放入後，將參考點向右移到空白處（若已達最右邊，則移至向上一排的最左邊），開始試下一片；沒有拼片能夠成功拼上，則將上一步改用不同拼片或擺法。重複以上過程，直到試出答案為止。
題外話：做這個的前一天晚上完全睡不著，滿腦子都是這個要怎麼寫，像是「這個寫法會炸，那這樣呢？」。隔天早上一起床（雖然沒睡）就開始動工，結果只花了一個上午就完成了。興頭的力量真可怕。
範例測資：
F
FF
A00
A000
0A000
00A000
all0
AFall0：以下都是0（未填滿空位），因為後面的題目大多都只有上面兩塊，打一堆0很麻煩。
AF：已使用積木代號（注意A跟F之間沒有空格）。
以下是程式碼：
#include<set>
#include<string>
#include<iostream>
//global value
std::set<char> unused = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'};
char map[10][10] = {{ '0','0','0','0','0','0','0','0','0','0'},
{ '0','0','0','0','0','0','0','0','0','1'},
{ '0','0','0','0','0','0','0','0','1','1'},
{ '0','0','0','0','0','0','0','1','1','1'},
{ '0','0','0','0','0','0','1','1','1','1'},
{ '0','0','0','0','0','1','1','1','1','1'},
{ '0','0','0','0','1','1','1','1','1','1'},
{ '0','0','0','1','1','1','1','1','1','1'},
{ '0','0','1','1','1','1','1','1','1','1'},
{ '0','1','1','1','1','1','1','1','1','1'}};
int fuck = 0;
void printPyramid()
{
for (int i = 9; i >= 0; i--)
{
for (int j = 0; j < i; j++)
printf(" ");
for (int j = 0; j <= 9-i; j++)
printf("%c ", map[i][j]);
printf("\n");
}
}
//check if it's ok to put certain piece at certain angle
bool canBePut(int y, int x, int ballY[], int ballX[], int ballNum)
{
for (int i = 0; i < ballNum; i++)
{
//printf("y:%d x:%d y+:%d x+:%d \n", y, x, ballY[i], ballX[i]);
if (y + ballY[i] >= 10 || y + ballY[i] < 0 || x + ballX[i] >= 10 || x + ballX[i] < 0|| map[y + ballY[i]][x + ballX[i]] != '0')
{
return false;
}
}
//printf("it's my hollllleeeeeeee!!!\n");
return true;
}
//find the next refer-point
void nextPoint(int &y, int &x)
{
while (map[y][x] != '0')
{
x++;
if (x > 9)
{
x = 0;
y++;
}
if (x > 0 && y == 9)
{
x = 0;
y = 0;
printPyramid();
printf("!!!%d:fuck!!!\n", fuck);
break;
}
}
return;
}
int yArray[60][4] = {
/*A*/
{ 1, 2, 3, 0 },
{ 1, 2, 3, 0 },
{ 1, 1, 2, 0 },
{ 1, 1, 2, 0 },
{ 1, 2, 3, 0 },
{ 1, 1, 2, 0 },
{ 1, 2, 3, 0 },
{ 1, 1, 2, 0 },
/*B*/
{ 1, 2, 2, 3 },
{ 0, 1, 1, 2 },
{ 1, 2, 2, 3 },
{ 1, 1, 2, 2 },
{ 1, 1, 2, 2 },
{ 1, 1, 2, 3 },
{ 1, 1, 2, 3 },
{ 0, 1, 1, 2 },
/*C*/
{ 1, 2, 3, 4 },
{ 1, 2, 3, 4 },
{ 1, 1, 2, 3 },
{ 1, 1, 2, 3 },
{ 1, 2, 3, 4 },
{ 1, 2, 2, 3 },
{ 1, 2, 3, 4 },
{ 1, 2, 2, 3 },
/*D*/
{ 0, 1, 2, 3 },
{ 0, 1, 2, 3 },
{ 1, 2, 2, 3 },
{ 1, 2, 2, 3 },
{ 1, 2, 3, 3 },
{ 1, 1, 2, 3 },
{ 1, 2, 3, 3 },
{ 1, 1, 2, 3 },
/*E*/
{ 0, 1, 1, 2 },
{ 1, 2, 3, 4 },
{ 1, 2, 3, 4 },
{ 0, 1, 1, 2 },
{ 1, 2, 3, 4 },
{ 1, 1, 2, 2 },
{ 1, 2, 3, 4 },
{ 1, 1, 2, 2 },
/*F*/
{ 0, 1, 0, 0 },
{ 1, 2, 0, 0 },
{ 1, 2, 0, 0 },
{ 1, 1, 0, 0 },
/*G*/
{ 1, 2, 3, 4 },
{ 1, 2, 3, 4 },
{ 0, 1, 1, 2 },
{ 1, 1, 2, 2 },
/*H*/
{ 0, 0, 1, 1 },
{ 1, 2, 3, 4 },
{ 1, 2, 3, 4 },
{ 0, 1, 1, 1 },
/*I*/
{ 1, 2, 2, 3 },
{ 1, 2, 2, 3 },
{ 1, 1, 2, 3 },
{ 1, 1, 2, 3 },
/*J*/
{ 1, 2, 3, 0 },
{ 1, 2, 3, 0 },
/*K*/
{ 1, 1, 2, 0 },
/*L*/
{ 0, 1, 2, 2 } };
int xArray[60][4] = {
/*A*/
{ 0,-1,-2, 0 },
{-1,-1,-1, 0 },
{-1, 0, 0, 0 },
{ 0,-1,-2, 0 },
{ 0, 0,-1, 0 },
{ 0, 1, 0, 0 },
{-1,-2,-2, 0 },
{-1,-2,-2, 0 },
/*B*/
{-1,-1,-2,-2 },
{ 1, 0, 1, 0 },
{ 0, 0,-1,-1 },
{ 0,-1,-1,-2 },
{ 0,-1,-1, 0 },
{ 0,-1,-1,-2 },
{ 0,-1,-1,-1 },
{ 1, 0,-1,-1 },
/*C*/
{-1,-1,-1,-1 },
{ 0,-1,-2,-3 },
{-1, 0, 0, 0 },
{ 0,-1,-2,-3 },
{ 0, 0, 0,-1 },
{ 0, 0, 1, 0 },
{-1,-2,-3,-3 },
{-1,-2,-3,-3 },
/*D*/
{ 1, 0,-1,-2 },
{ 1, 0, 0, 0 },
{ 0,-1, 0, 0 },
{-1,-1,-2,-3 },
{ 0, 0, 0,-1 },
{ 0, 1, 0, 0 },
{-1,-2,-2,-3 },
{-1,-2,-2,-3 },
/*E*/
{ 1, 0, 1, 1 },
{ 0,-1,-1,-1 },
{-1,-1,-2,-3 },
{-1,-1,-2,-3 },
{ 0, 0,-1,-1 },
{ 0, 1, 0, 1 },
{-1,-2,-2,-3 },
{-1,-2,-2,-3 },
/*F*/
{ 1, 0, 0, 0 },
{ 0,-1, 0, 0 },
{-1,-1, 0, 0 },
{ 0,-1, 0, 0 },
/*G*/
{ 0, 0,-1,-2 },
{-1,-2,-2,-2 },
{ 2, 0, 1, 0 },
{ 0,-1, 0,-2 },
/*H*/
{ 1, 2, 0, 1 },
{-1,-1,-2,-2 },
{ 0,-1,-1,-2 },
{ 1, 0,-1, 1 },
/*I*/
{-1, 0,-1,-1 },
{ 0,-1,-2,-2 },
{ 0,-1,-2,-2 },
{ 0,-1, 0,-1 },
/*J*/
{ 0, 0, 0, 0 },
{-1,-2,-3, 0},
/*K*/
{ 0,-1,-1, 0 },
/*L*/
{ 1, 0, 0,-1 } };
char piece[60] = { 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B',
'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C',
'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D',
'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E',
'F', 'F', 'F', 'F', 'G', 'G', 'G', 'G',
'H', 'H', 'H', 'H', 'I', 'I', 'I', 'I',
'J', 'J', 'K', 'L' };
//dfs
bool put(int y, int x)
{
int ballSize;
int newX, newY;
for (int t = 0; t < 60; t++)
{
if (unused.empty())
{
printf("how the fuck???!!!\n");
return true;
}
if (unused.count(piece[t]))
{
switch (piece[t])
{
case 'F':
ballSize = 2;
break;
case 'A':
case 'J':
case 'K':
ballSize = 3;
break;
default:
ballSize = 4;
break;
}
if (canBePut(y, x, yArray[t], xArray[t], ballSize))
{
map[y][x] = piece[t];
for (int i = 0; i < ballSize; i++)
{
map[y + yArray[t][i]][x + xArray[t][i]] = piece[t];
}
unused.erase(piece[t]);
newX = x;
newY = y;
nextPoint(newY, newX);
if (newX == 0 && newY == 0)
//return false;
return true;
if (!put(newY, newX))//undo
{
map[y][x] = '0';
for (int i = 0; i < ballSize; i++)
{
map[y + yArray[t][i]][x + xArray[t][i]] = '0';
}
unused.insert(piece[t]);
}
else
//return false;
return true;
}
}
}
//printPyramid();
//printf("!!!%d:fuck!!!\n", fuck);
fuck++;
return false;
}
int main()
{
int x = 0;
int y = 9;
//input
std::string sin;
while (std::cin >> sin)
{
if (sin == "all0")
break;
for (int i = 0; i < sin.length(); i++)
map[y][i] = sin[i];
y--;
if (y < 0)
break;
}
std::cin >> sin;
for (int i = 0; i < sin.length(); i++)
unused.erase(sin[i]);
//show the question
printPyramid();
printf("unused:");
for (const auto& ch : unused)
{
std::cout << ch << " ";
}
printf("\n");
y = 0;
if (map[y][x] != '0')
nextPoint(y, x);
//dfs
if(put(y,x))
printf("hell yeah!");
else
printf("no way!");
return 0;
}
/*test input
#1
F
FF
A00
A000
0A000
00A000
all0
AF
#2
B
BB
BB0
A000
AA000
00A000
all0
AB
#3
I
II
IB0
AIB0
AABB0
A00B00
D000000
D0000000
D00000000
DD00000000
IBAD
*/
留言
張貼留言
請避免辱罵、洗版，要不像有智慧的人一樣辯論，要不把反對的聲音留在自己身邊。