a562 - ITSA201112 P2 小白鼠走方格
題目描述
題目要求找出在一個 m x m 的方陣中，小白鼠可以行經的最長路徑。小白鼠可以上下左右移動，但不能對角移動，且不能重複經過同一個格子，也不能經過數字相同的格子。
解題思路
這題可以使用深度優先搜尋 (DFS) 搭配回溯法來解決。對於每個格子，我們嘗試向四個方向移動，如果移動後的格子合法（即在方陣範圍內、未被走過、數字不相同），則繼續 DFS。在 DFS 的過程中，我們記錄目前路徑的長度，並更新最長路徑的長度。當 DFS 到達終止條件（例如，無法繼續移動或路徑長度不優於目前最長路徑）時，我們回溯到上一個格子，嘗試其他方向的移動。
程式碼中，r[a[x][y]] 用於記錄數字 a[x][y] 是否已被走過，f[x][y] 用於記錄格子 (x, y) 是否已被走過。rc[a[x][y]] 記錄數字 a[x][y] 出現的次數，用於判斷是否可以走過。ans 記錄目前找到的最長路徑長度。dfs 函數實現了 DFS 算法，main 函數負責讀取輸入、初始化資料和輸出結果。
複雜度分析
- 時間複雜度: O(m^4)，其中 m 是方陣的邊長。在最壞的情況下，DFS 可能會遍歷所有可能的路徑，而每條路徑的長度最多為 m x m。
- 空間複雜度: O(m^2)，主要用於儲存
f陣列（記錄是否走過）和r陣列（記錄數字是否走過）。rc陣列的大小為 O(101)，可以視為常數空間。
程式碼
#include <iostream>
using namespace std;
int ans,a[10][10],n,c,r[105],f[10][10],rc[105];
void dfs(int x,int y,int v,int p){
if(x<0||y<0||x>=n||y>=n||r[a[x][y]]||f[x][y]||p+v<=ans)return;
f[x][y]=r[a[x][y]]=1;
p-=rc[a[x][y]];
ans = max(ans,v);
dfs(x-1,y,v+1,p);
dfs(x+1,y,v+1,p);
dfs(x,y+1,v+1,p);
dfs(x,y-1,v+1,p);
f[x][y]=r[a[x][y]]=0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> c;
while(c--){
cin >> n;
for(int i=0;i<101;++i)
r[i]=rc[i]=0;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
f[i][j]=0;
cin >> a[i][j];
++rc[a[i][j]];
}
ans=0;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
dfs(i,j,1,n*n);
cout << ans << '\n';
}
}