b841 - 104北二5.骨牌遊戲
題目描述
題目要求在一個 H x W 的棋盤上，找出可以配對的骨牌的最大數量。骨牌由兩個數值相同且相鄰的格子組成，相鄰指的是水平或垂直方向。
解題思路
這題可以使用深度優先搜尋 (DFS) 或回溯法來解決。基本思路是遍歷棋盤，如果找到可以配對的骨牌，則將它們標記為已使用，並遞迴地尋找剩餘棋盤上的骨牌。在遞迴的每一步，記錄目前找到的骨牌數量，並更新最大值。回溯時，將標記為已使用的骨牌恢復原狀，以便探索其他可能的配對方案。
程式碼首先讀取棋盤的尺寸和數值。然後，它遍歷棋盤的每個格子，檢查是否可以形成水平或垂直的骨牌。如果可以，則將骨牌標記為已使用，並遞迴地尋找剩餘棋盤上的骨牌。在遞迴過程中，更新最大骨牌數量。最後，回溯時將骨牌恢復原狀，以便探索其他可能的配對方案。
複雜度分析
- 時間複雜度: O(2^(H*W))，在最壞情況下，需要嘗試所有可能的骨牌配對組合。
- 空間複雜度: O(H*W)，主要用於儲存棋盤和遞迴呼叫堆疊。
程式碼
#include <iostream>
using namespace std;
int n,m,a[10][10],ans;
bool jr(int x,int y,int t){
if(a[x][y]==0)return 0;
if(t){// ->
if(y>=m-1)return 0;
if(a[x][y+1]==0)return 0;
if(a[x][y]!=a[x][y+1])return 0;
return 1;
}
else{
if(x>=n-1)return 0;
if(a[x+1][y]==0)return 0;
if(a[x][y]!=a[x+1][y])return 0;
return 1;
}
}
void dfs(int x,int y,int s){
ans=max(s,ans);
int st=y;
for(int i=max(x-1,0);i<n;++i){
for(int j=st;j<m;++j){
if(jr(i,j,0)){
int tmp=a[i][j];
a[i][j]=a[i+1][j]=0;
dfs(i,j+1,s+1);
a[i][j]=a[i+1][j]=tmp;
}
else if(jr(i,j,1)){
int tmp=a[i][j];
a[i][j]=a[i][j+1]=0;
dfs(i,j+1,s+1);
a[i][j]=a[i][j+1]=tmp;
}
}
st=0;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin >> a[i][j];
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(jr(i,j,0)){
int tmp=a[i][j];
a[i][j]=a[i+1][j]=0;
dfs(i,j+1,1);
a[i][j]=a[i+1][j]=tmp;
}
else if(jr(i,j,1)){
int tmp=a[i][j];
a[i][j]=a[i][j+1]=0;
dfs(i,j+1,1);
a[i][j]=a[i][j+1]=tmp;
}
}
}
cout << ans;
}