CSP考試復習：第三單元 3.5 Mayan 游戲

題目描述

Mayan puzzle 是最近流行起來的一個游戲，游戲界面是一個77 行 \times5×5 列的棋盤，上面堆放著一些方塊，方塊不能懸空堆放，即方塊必須放在最下面一行，或者放在其他方塊之上，游戲通關是指在規定的步數內消除所有的方塊，消除方塊的規則如下：

1. 每步移動可以且僅可以沿橫向（即向左或向右）拖動某一方塊一格：當拖動這一方塊時，如果拖動后到達的位置（以下稱目標位置）也有方塊，那么這兩個方塊將交換位置（參見輸入輸出樣例說明中的圖 66 到圖 77）；如果目標位置上沒有方塊，那么被拖動的方塊將從原來的豎列中抽出，并從目標位置上掉落（直到不懸空，參見下面圖 11 和圖 22）；

1. 任一時刻，如果在一橫行或者豎列上有連續三個或者三個以上相同顏色的方塊，則它們將立即被消除（參見圖1 到圖3），

注意：

a) 如果同時有多組方塊滿足消除條件，幾組方塊會同時被消除（例如下面圖 44，三個顏色為 11 的方塊和三個顏色為 22 的方塊會同時被消除，最后剩下一個顏色為 22 的方塊），

b) 當出現行和列都滿足消除條件且行列共享某個方塊時，行和列上滿足消除條件的所有方塊會被同時消除（例如下面圖5 所示的情形，55 個方塊會同時被消除），

1. 方塊消除之后，消除位置之上的方塊將掉落，掉落后可能會引起新的方塊消除，注意：掉落的程序中將不會有方塊的消除，

上面圖 11 到圖 33 給出了在棋盤上移動一塊方塊之后棋盤的變化，棋盤的左下角方塊的坐標為 (0,0)(0,0)，將位于 (3,3)(3,3) 的方塊向左移動之后，游戲界面從圖 11 變成圖 22 所示的狀態，此時在一豎列上有連續三塊顏色為 44 的方塊，滿足消除條件，消除連續 33 塊顏色為 44 的方塊后，上方的顏色為 33 的方塊掉落，形成圖 33 所示的局面，

輸入格式

共 66 行，

第一行為一個正整數 nn，表示要求游戲通關的步數，

接下來的 55 行，描述 7 \times 57×5 的游戲界面，每行若干個整數，每兩個整數之間用一個空格隔開，每行以一個 00 結束，自下向上表示每豎列方塊的顏色編號（顏色不多于 1010 種，從 11 開始順序編號，相同數字表示相同顏色），

輸入資料保證初始棋盤中沒有可以消除的方塊，

輸出格式

如果有解決方案，輸出 nn 行，每行包含 33 個整數 x,y,gx,y,g，表示一次移動，每兩個整數之間用一個空格隔開，其中 (x,y)(x,y) 表示要移動的方塊的坐標，gg 表示移動的方向，11 表示向右移動，-1?1 表示向左移動，注意：多組解時，按照 xx 為第一關鍵字，yy 為第二關鍵字，11 優先于 -1?1，給出一組字典序最小的解，游戲界面左下角的坐標為 (0,0)(0,0)，

如果沒有解決方案，輸出一行 -1，

說明/提示

【輸入輸出樣例說明】

按箭頭方向的順序分別為圖 66 到圖 1111

樣例輸入的游戲局面如上面第一個圖片所示，依次移動的三步是：(2,1)(2,1) 處的方格向右移動，(3,1)(3,1) 處的方格向右移動，(3,0)(3,0) 處的方格向右移動，最后可以將棋盤上所有方塊消除，

【資料范圍】

對于 30\%30% 的資料，初始棋盤上的方塊都在棋盤的最下面一行；

對于 100\%100% 的資料，0<n \le 50<n≤5，

題目很長啊~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

【分析】
問題的性質加上 3s 的運行時間告訴我們：這個世界需要暴力，
一個塊向右交換，與它右邊的塊向左交換是等價的，但前者的字典序更小，所以不必考慮后者，
此外，如果一種顏色的數量在 1～2 之間，就可以直接剪枝，
與其說本題在考察搜索，不如說本題在考察選手的編程習慣和心理素質，很多人沒有清晰明確的思路和良
好的編碼習慣，結果“投降”，輸出了“-1”，或者寫了數 KB 代碼卻沒有得到多少分，所以大家要養成好的編
程習慣，包括變數的命名、代碼縮進、注釋等，同時要發揚敢于使用暴力的精神，
【代碼】
下面代碼沒有任何剪枝，但已經測驗通過了，

#include <iostream>
#include <cstring>
using namespace std;
inline void swap(int &a, int &b) { int t=a; a=b; b=t; }
// 程式中使用橫向棋盤，5行7列，水平移動變豎直移動，豎直移動變水平運動，
int n;
int map[7][6][9];
int a[6],b[6],c[6]; // 每一步的變化，a是棋盤倒放之后的行，b是列
// 方塊下落
void fall(int depth)
{
for (int i=1; i<=5; i++)
{
int *m=map[depth][i];
// 在第i行中，尋找第一個0，然后再尋找非0，接下來移動，不過不一定正確……
int j=1,k=0;
while (m[j]) j++;
if (j==8) continue;
k=j+1;
while (m[k]==0 && k<8) k++;
while (k<8) swap(m[j++],m[k++]);
}
}
// 檢查是否可以消除方塊，如果可以，就消除方塊，
bool mark[6][8]; // 消除方塊時用
bool check(int depth)
{
bool changed=false;
memset(mark,0,sizeof(mark));
// 檢查是否可以消除
// 水平方向
for (int i=1; i<=5; i++)
for (int delta=7; delta>=3; delta--) // 連通的方塊數
for (int j=1; j<=8-delta; j++)
{
int a=map[depth][i][j];
for (int k=j+1; k<=j+delta-1; k++)
if (map[depth][i][k]!=a)
{
a=0;
break;
}
if (a) for (int k=j; k<=j+delta-1; k++) mark[i][k]=true;
}
// 豎直方向
for (int j=1; j<=7; j++)
for (int delta=5; delta>=3; delta--)
for (int i=1; i<=6-delta; i++)
{
int a=map[depth][i][j];
for (int k=i+1; k<=i+delta-1; k++)
if (map[depth][k][j]!=a)
{
a=0;
break;
}
if (a) for (int k=i; k<=i+delta-1; k++) mark[k][j]=true;
}
// 消除
for (int i=1; i<=5; i++)
for (int j=1; j<=7; j++)
if (mark[i][j]) map[depth][i][j]=0, changed=true;
return changed;
}
// 進行搜索，如果有解則回傳true，否則回傳false，
bool DFS(int depth)
{
if (depth>n)
{
for (int i=1; i<=5; i++)
if (map[n+1][i][1]) return false;
return true;
}
for (int i=1; i<=5; i++)
for (int j=1; j<=7; j++)
{
/*
移動一種方塊，分四種情況：
① 方塊本身就是0，那么直接跳過；
② 在左邊界，只能向右移動；
③ 在右邊界，只能向左移動，如果左邊有方塊，那么可以忽略這一步，
因為那個方塊右移和這個方塊左移效果相同，但字典序更小，
也就是說，在右邊界時，如果左邊為空，則向左移動，否則不移動，
④ 不在邊界，如果左邊為空，就既向左又向右（特殊考慮，因為要多一段代碼）；
如果左邊不為空，那么不管右邊是什么都向右移動，
*/
if (map[depth][i][j]==0) continue;
a[depth]=i;
b[depth]=j;
int &dir=c[depth]; // 移動方向
if (i<5) // 第②種情況＋第④種情況的第一部分
dir=1;
else if (i==5 && map[depth][4][j]==0) // 第③種情況
dir=-1;
else
continue;
memcpy(map[depth+1], map[depth], sizeof(map[depth]));
swap(map[depth+1][i][j], map[depth+1][i+dir][j]);
// 下落與消除方塊
do
{
fall(depth+1);
} while (check(depth+1));
// 繼續搜索
if (DFS(depth+1)) return true;
if (i>1 && i<5 && map[depth][i-1][j]==0) // 第④種情況的第二部分
{
a[depth]=i;
b[depth]=j;
dir=-1;
memcpy(map[depth+1], map[depth], sizeof(map[depth]));
swap(map[depth+1][i][j], map[depth+1][i+dir][j]);
// 和上面一樣
do
{
fall(depth+1);
} while (check(depth+1));
if (DFS(depth+1)) return true;
}
}
return false;
}
int main()
{
memset(map,0,sizeof(map));
cin>>n;
for (int i=1; i<=5; i++)
{
int temp, j=1;
do
{
cin>>temp;
map[1][i][j++]=temp;
} while (temp);
}
if (DFS(1))
for (int i=1; i<=n; i++)
cout<<(a[i]-1)<<" "<<(b[i]-1)<<" "<<c[i]<<endl;
else
cout<<"-1"<<endl;
return 0;
}

這都4000多字了~~~