HDU 5024 Wang Xifeng's Little Plot：枚舉轉彎點 + 記憶化 DFS 求最長單轉彎路徑

題目大意

N×N（N ≤ 100）網格，'.' 為路，'#' 為障礙。從一格走到另一格允許 8 方向。路徑最多只能轉一次 90°彎（含斜向直角）。求最長路徑長度（格子數）。

解題思路

1. 枚舉所有可能的轉彎點與轉彎方向組合（8 種直角：4 正交 + 4 斜向）。
2. 對每個轉彎點，沿兩個方向分別 DFS 計算可延伸長度，記憶化 dp[x][y][dir] 表示從 (x,y) 沿 dir 方向連續 '.' 的長度。
3. 路徑長度 = len1 + len2 - 1（轉彎點重複計算一次）。取最大值。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int dx[8] = {0,-1,0,1,-1,1,1,-1};
int dy[8] = {-1,0,1,0,-1,-1,1,1};
int dp[MAXN][MAXN][8], n, ans;
char g[MAXN][MAXN];

int dfs(int x, int y, int dir) {
    int &res = dp[x][y][dir];
    if (res != -1) return res;
    int nx = x + dx[dir], ny = y + dy[dir];
    if (nx < 0 || nx >= n || ny < 0 || ny >= n || g[nx][ny] != '.') return res = 1;
    return res = 1 + dfs(nx, ny, dir);
}

void check(int x, int y, int d1, int d2) {
    ans = max(ans, dfs(x, y, d1) + dfs(x, y, d2) - 1);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> g[i];
        memset(dp, -1, sizeof(dp));
        ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (g[i][j] == '.')
                    for (int k = 0; k < 4; ++k) {
                        check(i, j, k, (k+1)%4);         // 正交
                        check(i, j, 4+k, 4+(k+1)%4);     // 斜向
                    }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 狀態數：N² × 8 ≤ 80,000，每狀態 O(1) 轉移。
• 總時間：O(N²)，極快。
• 空間：O(N²)。

關鍵點

• 8 方向編碼：0~3 為上右下左，4~7 為四個斜向。
• 直角組合：(k, (k+1)%4) 與 (4+k, 4+(k+1)%4) 覆蓋所有 90° 轉彎。
• 記憶化 DFS 避免重複計算，保證線性時間。