POJ 1154 LETTERS：DFS 入門尋找矩陣中最長不重複字符路徑

題目大意

給定 R×S 字符矩陣 (R,S ≤ 20)，從任意格子出發，上下左右移動，不重複訪問字符 (字符不重複，非格子)。求最長路徑長度 (字符數)。

DFS + 回溯 + 字符訪問標記

狀態：(r, c, len) 當前位置和路徑長度。
訪問標記：vis[256] 記錄字符是否已用 (ASCII 字符)。

遞歸框架

int R, S;
char grid[25][25];
bool vis[256];
int ans = 1;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void dfs(int r, int c, int len) {
    ans = max(ans, len + 1); // 當前字符已算入 len
    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= R || nc < 0 || nc >= S) continue;
        char ch = grid[nr][nc];
        if (vis[ch]) continue;
        vis[ch] = true;
        dfs(nr, nc, len + 1);
        vis[ch] = false;
    }
}

int main() {
    cin >> R >> S;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < S; ++j)
            cin >> grid[i][j];

    vis[grid[0][0]] = true;
    dfs(0, 0, 1);
    cout << ans << '\n';
    return 0;
}

關鍵點

• 字符去重：題目要求字符不重複，非格子不重複。用 vis[char] 而非 vis[r][c]
• 從 (0,0) 起步：題目隱含從左上角開始 (樣例/標準解法)。若任意起點，需雙循環嘗試所有起點
• 無需記憶化：狀態包含訪問字符集合 (2²⁶ 種)，無法 DP，純 DFS 回溯
• 剪枝：len + (未訪問字符數) ≤ ans 可剪枝，但 n≤20 通常不需

複雜度分析

• 最壞每步 4 選擇，深度 ≤ 26 (字符種類數)，O(4²⁶) 理論極大
• 實際字符重複多、邊界限制，搜索樹極小，毫秒級通過

完整代碼 (任意起點版)

#include <bits/stdc++.h>
using namespace std;

int R, C, ans;
char g[25][25];
bool used[256];
int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};

void dfs(int r, int c, int len) {
    ans = max(ans, len);
    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr<0||nr>=R||nc<0||nc>=C) continue;
        char ch = g[nr][nc];
        if (used[ch]) continue;
        used[ch] = true;
        dfs(nr, nc, len+1);
        used[ch] = false;
    }
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            cin >> g[i][j];

    ans = 0;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j) {
            memset(used, 0, sizeof(used));
            used[g[i][j]] = true;
            dfs(i, j, 1);
        }
    cout << ans << '\n';
    return 0;
}

總結

POJ 1154 是DFS 回溯入門經典題：矩陣搜索、字符級訪問標記、四方向擴展、全局最大值更新。掌握此模板，可解決「矩陣最長路徑、單詞搜索 (LeetCode 79)、數獨求解」等大批回溯問題。關鍵區別：字符不重複 vs 格子不重複，決定狀態空間大小與標記方式。