Codeforces Round #220 (Div. 2) C題：Inna and Dima - 記憶化搜索與動態規劃解法詳解

Codeforces Round #220 (Div. 2) C題：Inna and Dima - 記憶化搜索與動態規劃解法詳解

這是一道經典的動態規劃結合記憶化搜索的問題。題目要求在一個字符矩陣中尋找「DIMA」序列的最大重複次數，機器人可以上下左右移動，但不能重複訪問同一個格子形成環路。

核心思路

定義 dp[i][j] 表示從第 i 行第 j 列的格子出發，能夠走出的最大「DIMA」序列長度。採用以下狀態標記策略：

• -1：表示該狀態尚未計算
• INF（0x3f3f3f3f）：表示正在計算中（用於檢測環路）
• 正整數：已計算完成的最大長度

當 DFS 過程中遇到狀態為 INF 的格子時，說明發現了環路，直接返回 INF，最終輸出「Poor Inna!」。否則將所有起始位置為 'D' 的格子作為起點進行 DFS，取最大值除以 4 即為答案。

關鍵代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
char mp[1001][1001];
char str[] = "DIMA";
int dp[1001][1001];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m;

int dfs(int x, int y, int step) {
    if (dp[x][y] != -1) return dp[x][y];
    dp[x][y] = INF;  // 標記為正在訪問
    
    int nxt = (step + 1) % 4;
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && mp[nx][ny] == str[nxt]) {
            ans = max(ans, dfs(nx, ny, nxt));
        }
    }
    dp[x][y] = ans + 1;
    return dp[x][y];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", mp[i]);
    memset(dp, -1, sizeof(dp));
    
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 'D') {
                maxLen = max(maxLen, dfs(i, j, 0));
            }
        }
    }
    
    if (maxLen >= INF) puts("Poor Inna!");
    else if (maxLen < 4) puts("Poor Dima!");
    else printf("%d\n", maxLen / 4);
    return 0;
}

複雜度分析

時間複雜度：O(n × m)，每個格子最多被計算一次。空間複雜度：O(n × m)，用於存儲 DP 表和訪問標記。

常見陷阱提醒

注意處理無法形成完整「DIMA」序列的情況（最大長度小於 4 時輸出 "Poor Dima!"），以及環路檢測必須在遞歸入口處進行，否則會導致棧溢出或錯誤結果。