題目
#算法/進階搜索
思路:
根據題意,我們可以知道,這題只能枚舉,剪枝,因此,我們考慮如何枚舉,剪枝.
首先,我們要定義下降函數down(),使得小木塊右移時,能夠下降到最低處,其次,我們還需要寫出判斷函數,判斷矩陣內是否有小木塊沒被消除.另外,我們還需要消除函數,將矩陣內三個相連的小木塊清除,dfs()函數進行搜索

這里,我們定義數組橫坐標代表原矩陣的列,縱坐標代表原矩陣的行,坐標軸從1,1開始

check判斷函數:

直接判斷當前矩陣中是否仍存在小正方行

  bool check(){for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j])return false;}}return true;}

clear()清除函數

由于我們后序每次將正方行下降后都需要判斷當前是否需要清除,所以我們將clear定義為int,
判斷的時候,我們三個一組的判斷
1.先橫向判斷每一行是否有三個連續的
2.在豎向判斷是否有三個連續的
注意:這里我們全部判斷完后再進行刪除,否則會出現4-5個連續的同色方塊只能刪除三個
int clear(){int g=0;int del[10][10]={0};
橫向刪除for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(!dp[i][j])continue;if(i>1&&i<5){if(dp[i-1][j]==dp[i][j]&&dp[i][j]==dp[i+1][j]){del[i-1][j]=del[i][j]=del[i+1][j]=g=1;}}}}
豎向刪除for(int i=1;i<=5;i++){for(int j=2;j<=6;j++){if(dp[i][j]==0)continue;if(dp[i][j-1]==dp[i][j]&&dp[i][j]==dp[i][j+1]){del[i][j-1]=del[i][j]=del[i][j+1]=g=1;}}}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(del[i][j]==1)dp[i][j]=0;}}return g;}

down()下降函數

在下降的時候,會出現一列的小正方形多組不連續,比如1020201,我們在下降的時候需要先將第一個2下降到最底部,再將第二個2下降到最底部,最后將1下降到最底部,所以,我們從下往上降
void down(){for(int i=1;i<=5;i++){
從原矩陣第二行開始下降for(int j=2;j<=7;j++){if(dp[i][j]==0)continue;int k=j;這里一定要添加限定條件k-1>=1while(k-1>=1&&dp[i][k-1]==0){swap(dp[i][k],dp[i][k-1]);k--;}}}}

dfs()函數

定義flag代表我們是否找到可刪除合法方案

void dfs(int x){
如果已經刪除完了,直接返回if(flag)return;if(x>n){if(check()){for(int i=1;i<=n;i++){
res,0放原坐標軸x,1放原坐標y,2放正方向移動方向cout<<res[i][0]<<' '<<res[i][1]<<' '<<res[i][2]<<endl;}flag=true;}return;}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j]==0)continue;int tmp[10][10];
保存初始狀態memcpy(tmp,dp,sizeof(tmp));
正方行右移if(i<5){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=1;swap(dp[i][j],dp[i+1][j]);for(down();clear()!=0;down());dfs(x+1);
恢復初始狀態memcpy(dp,tmp,sizeof(dp));}
正方向左移if(i>=2){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=-1;swap(dp[i][j],dp[i-1][j]);for(down();clear()!=0;down());dfs(x+1);
恢復初始狀態memcpy(dp,tmp,sizeof(dp));}}}}

完整代碼

#include<iostream>#include<cstring>using namespace std;int n;int dp[10][10];int res[30][3];bool flag=false;bool check(){for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j])return false;}}return true;}int clear(){int g=0;int del[10][10]={0};for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(!dp[i][j])continue;if(i>1&&i<5){if(dp[i-1][j]==dp[i][j]&&dp[i][j]==dp[i+1][j]){del[i-1][j]=del[i][j]=del[i+1][j]=g=1;}}}}for(int i=1;i<=5;i++){for(int j=2;j<=6;j++){if(dp[i][j]==0)continue;if(dp[i][j-1]==dp[i][j]&&dp[i][j]==dp[i][j+1]){del[i][j-1]=del[i][j]=del[i][j+1]=g=1;}}}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(del[i][j]==1)dp[i][j]=0;}}return g;}void down(){for(int i=1;i<=5;i++){for(int j=2;j<=7;j++){if(dp[i][j]==0)continue;int k=j;while(k-1>=1&&dp[i][k-1]==0){swap(dp[i][k],dp[i][k-1]);k--;}}}}void dfs(int x){if(flag)return;if(x>n){if(check()){for(int i=1;i<=n;i++){cout<<res[i][0]<<' '<<res[i][1]<<' '<<res[i][2]<<endl;}flag=true;}return;}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j]==0)continue;int tmp[10][10];memcpy(tmp,dp,sizeof(tmp));if(i<5){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=1;swap(dp[i][j],dp[i+1][j]);for(down();clear()!=0;down());dfs(x+1);memcpy(dp,tmp,sizeof(dp));}if(i>=2){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=-1;swap(dp[i][j],dp[i-1][j]);for(down();clear()!=0;down());dfs(x+1);memcpy(dp,tmp,sizeof(dp));}}}}int main(void){cin>>n;for(int i=1;i<=5;i++){int cnt=1;int tmp;while(cin>>tmp&&tmp){dp[i][cnt]=tmp;cnt++;}}dfs(1);if(flag==false){cout<<-1<<endl;}return 0;}