題目描述

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

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

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

注意：

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

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

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

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

輸入格式

共 $6$ 行。

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

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

輸入數據保證初始棋盤中沒有可以消除的方塊。

輸出格式

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

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

輸入輸出樣例 #1

輸入 #1

3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0

輸出 #1

2 1 1
3 1 1
3 0 1

說明/提示

【輸入輸出樣例說明】

按箭頭方向的順序分別為圖 $6$ 到圖 $11$

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

【數據范圍】

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

對于 $100\%$ 的數據，$0<n\le 5$。

算法思路

• 狀態表示：
• 使用矩陣$m$存儲網格狀態，$m[i][j]$表示第$i$列第$j$行的顏色值（$1\le i\le 5,1\le j\le 7$）。
• 數組$num[i]$記錄第$i$列當前方塊數量。
• 操作序列用$x[],y[],yi[]$分別存儲行、列和方向（$?1$左移，$1$右移）。

核心函數：

• 消除檢測（sd）：掃描全圖，標記水平或垂直連續三個及以上同色方塊為$0$（消除）。返回是否發生消除。 $$\text{檢測條件：}\{\begin{array}{llc}m[i][j]=m[i\pm 1][j]\ne 0& \text{（垂直）}m[i][j]=m[i][j\pm 1]\ne 0& \text{（水平）}\end{array}$$
• 下落處理（xia）：消除后，每列方塊下落填補空隙，更新$num$數組。
• 連鎖消除（find）：遞歸調用sd和xia，直到無更多消除。
• 深度優先搜索（dfs）：
• 終止條件：剩余步數$js=0$時，若所有$num[i]=0$則找到解（$flag=1$）。
• 狀態轉移：遍歷每個方塊，嘗試與左右相鄰方塊交換（需邊界檢查），執行連鎖消除后遞歸搜索$js?1$步。
• 回溯機制：每次嘗試前保存$m$和$num$狀態，遞歸返回后恢復。

剪枝優化：

• 當$flag=1$時立即返回，避免無效搜索。
• 優先嘗試可行操作，減少狀態空間。

復雜度分析

• 時間復雜度：最壞情況$O((5\times 7{)}^n)$，每層遞歸嘗試最多$5\times 7\times 2=70$種操作（$n$步操作）。
• 空間復雜度：$O(1)$，狀態備份使用固定大小數組。

優化建議

• 剪枝增強：記錄已訪問狀態哈希，避免重復搜索。
• 啟發式搜索：優先選擇可能觸發更多消除的操作。
• 迭代加深：當$n$較大時，改用IDDFS（迭代加深DFS）控制深度。
• 該解法通過DFS枚舉所有操作序列，結合回溯和狀態恢復，確保在有限步數內找到可行解。注意網- - 格行列索引從$0$開始輸出，方向$?1$/$1$對應左/右移動。

詳細代碼

#include<bits/stdc++.h>
#define int long long
#define pi pair<int,int>
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
using namespace std;
int n,m[10][10],x[6],y[6],yi[6],num[10],a,flag;
bool vis[10][10];
bool check()
{for(int i=1;i<=5;i++)if(num[i])return 0;return 1;
}
bool sd()
{int m1[10][10];memcpy(m1,m,sizeof(m1));bool ff=0;for(int i=1;i<=5;i++)for(int j=1;j<=7;j++){if(m1[i][j]==m1[i-1][j]&&m1[i][j]==m1[i+1][j]&&m1[i][j]!=0)m[i][j]=0,m[i-1][j]=0,m[i+1][j]=0,ff=1;if(m1[i][j]==m1[i][j+1]&&m1[i][j]==m1[i][j-1]&&m1[i][j]!=0)m[i][j]=0,m[i][j+1]=0,m[i][j-1]=0,ff=1;}return ff;
}
void xia()
{int m1[10][10];memcpy(m1,m,sizeof(m1));memset(m,0,sizeof(m));for(int i=1;i<=5;i++){int js=0;for(int j=1;j<=7;j++){if(m1[i][j])m[i][++js]=m1[i][j];}num[i]=js;}
}
void find()
{if(sd()){xia();find();return;}
}
void dfs(int js)
{
//	for(int i=1;i<=5;i++)
//	{
//		for(int j=1;j<=num[i];j++)
//			cout<<num[i];
//		cout<<'\n';
//	}
//	cout<<"-----------------------------"<<'\n';if(js==0&&check()){flag=1;return;}if(js==0)return;int m1[10][10],nn[10];memcpy(m1,m,sizeof(m1));memcpy(nn,num,sizeof(nn));for(int i=1;i<=5;i++)for(int j=1;j<=nn[i];j++){if(i>1&&!m[i-1][j]){swap(m[i-1][j],m[i][j]);xia();find();x[js]=i;y[js]=j;yi[js]=-1;dfs(js-1);if(flag)return;memcpy(num,nn,sizeof(num));memcpy(m,m1,sizeof(m));}if(i<5){swap(m[i][j],m[i+1][j]);xia();find();x[js]=i;y[js]=j;yi[js]=1;dfs(js-1);if(flag)return;memcpy(num,nn,sizeof(num));memcpy(m,m1,sizeof(m));}}
}
signed main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=5;i++){while(cin>>a&&a!=0){m[i][++num[i]]=a;}}dfs(n);if(flag)for(int i=n;i>=1;i--)cout<<x[i]-1<<" "<<y[i]-1<<" "<<yi[i]<<'\n';elsecout<<-1;return 0;
}