e431 - 不交錯一筆走完
題目描述
題目要求計算在一個 m x n 的網格中，從任意一個格子開始，不重複地走遍所有格子，並且只允許上下左右移動的合法路徑數量。需要注意的是，只計算起點和終點對調的路徑為同一種路徑，且翻轉後的路徑視為不同的路徑。
解題思路
這題使用深度優先搜尋 (DFS) 來枚舉所有可能的路徑。dfs 函數遞迴地探索從當前格子出發的所有可能的下一步，並記錄已經走過的格子。當走過的格子數量等於網格中的總格子數量時，表示找到一條合法的路徑，計數器 ans 增加。為了避免重複計算，只計算從每個起點開始的路徑，並將結果除以 2，因為起點和終點對調的路徑是等價的。
複雜度分析
- 時間複雜度: O(4^(m*n))。在最壞的情況下，DFS 需要探索所有可能的路徑，每個格子最多有四個方向可以走，因此時間複雜度是指數級的。
- 空間複雜度: O(m*n)。空間複雜度主要來自於遞迴調用的堆疊空間，以及
a陣列用於記錄訪問過的格子。
程式碼
#include <iostream>
using namespace std;
int m,n,a[13][13],t,ans;
void dfs(int x,int y,int step){
if(x>=m||y>=n||x<0||y<0||a[x][y])return;
if(step==t)++ans;
a[x][y]=1;
dfs(x+1,y,step+1);
dfs(x-1,y,step+1);
dfs(x,y+1,step+1);
dfs(x,y-1,step+1);
a[x][y]=0;
}
int main(){
while(cin >> m >> n){
t=m*n;
ans=0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
a[i][j]=0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
dfs(i,j,1);
cout << ans/2 << "\n";
}
}