HDU 1501 Zipper：DFS 判斷字符串交織（另一版本）

問題描述

同 ID 4560，給定三字符串 A,B,C，判斷 C 是否由 A,B 交織而成，順序保持。

DFS + 記憶化

狀態 (i, j) 表示 A 用了 i 字符，B 用了 j 字符。轉移：若 C[i+j] == A[i] 試 (i+1,j)；若 C[i+j] == B[j] 試 (i,j+1)。vis[i][j] 防重複。

代碼實現

#include 
#include 
using namespace std;
char A[205], B[205], C[405];
int vis[205][205], la, lb, lc, flag;

void dfs(int i, int j) {
    if (vis[i][j]) return;
    if (i == la && j == lb) { flag = 1; return; }
    vis[i][j] = 1;
    if (i < la && C[i+j] == A[i]) dfs(i+1, j);
    if (j < lb && C[i+j] == B[j]) dfs(i, j+1);
}

int main() {
    int T; scanf("%d", &T);
    for (int cs=1; cs<=T; ++cs) {
        scanf("%s%s%s", A, B, C);
        la = strlen(A); lb = strlen(B); lc = strlen(C);
        memset(vis, 0, sizeof(vis));
        flag = 0;
        if (A[la-1]==C[lc-1] || B[lb-1]==C[lc-1]) dfs(0,0);
        printf("Data set %d: %s\n", cs, flag ? "yes" : "no");
    }
}

與 ID 4560 版本差異

• 參數簡化：只傳 (i,j)，長度由 i+j 推導。
• 剪枝：先檢查最後一字符是否匹配，不匹配直接 no。
• 邏輯等價，風格略異。