b554 - 5.貪吃龍遊戲
題目描述
題目要求找出一個 n x n 的棋盤中，從左上角 (0, 0) 開始，可以連通的最大「1」的數量。連通的定義是上下左右相鄰。如果左上角是「0」，則輸出 0。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。從左上角開始，如果格子是「1」且未被訪問過，則標記為已訪問，並遞迴地向四個方向 (上、下、左、右) 搜尋。在遞迴過程中，記錄目前連通的「1」的數量。每次到達邊界或遇到「0」或已訪問過的格子時，更新最大連通數。使用 backtracking 的方式，在回溯時將格子標記為未訪問，以便其他路徑可以通過該格子。
複雜度分析
- 時間複雜度: O(n^2) 因為最壞的情況下，DFS 需要遍歷整個棋盤。
- 空間複雜度: O(n^2) 主要來自於
vis陣列，用於記錄訪問過的格子，以及 DFS 的遞迴堆疊空間，在最壞情況下遞迴深度可能達到 n^2。
程式碼
#include <cstdio>
#define max(x,y) ((x)>(y)?(x):(y))
int n, ans(-1);
bool arr[7][7], vis[7][7]{};
void dfs(int i, int j, int step){
if(i < 0 || j < 0 || i >= n || j >= n){
ans = max(ans, step - 1);
return;
}
if(!arr[i][j] || vis[i][j])
ans = max(ans,step - 1);
else{
vis[i][j] = 1;
dfs(i - 1, j, step + 1);
dfs(i + 1, j, step + 1);
dfs(i, j - 1, step + 1);
dfs(i, j + 1, step + 1);
vis[i][j] = 0;
}
}
int main(){
scanf("%d", &n); getchar();
for(int i = 0, t; i < n; getchar(), i++)
for(int j = 0; j < n; arr[i][j] = t - '0', j++)
t = getchar_unlocked();
dfs(0, 0, 1);
printf("%d", ans);
return 0;
}