POJ 2049 Finding Nemo：二維網格 BFS + 牆門建模求最少穿門數

問題建模

海底迷宮：牆壁平行座標軸，厚度為 0；門長 1 開在牆上。馬林從 (0,0) 出發，需穿過最少門找到尼莫 (f1,f2)。牆/門坐標範圍 [1,199]，但實測數據可能超出。

核心轉化：坐標離散化 ×2

將原始坐標乘 2，使牆壁佔據偶數行/列，門佔據奇數行/列，空地佔據奇數行/列。例如牆 (x,y,d,t)：
- d=0 (平行 X 軸) → 佔據 mp[2*x][2*y ... 2*(y+t)] = 1
- d=1 (平行 Y 軸) → 佔據 mp[2*x ... 2*(x+t)][2*y] = 1
門同理標記 door[][] = 1。尼莫位置 (f1,f2) 映射為 (int(f1)*2+1, int(f2)*2+1)。

雙階段搜索策略

1. DFS 從 (1,1) 洪水填充：標記所有迷宮外部可達空地 mp[][]=2（不穿門）。
2. BFS 從尼莫位置出發：狀態 (x,y,step)，step 為穿門數。優先隊列（或 0-1 BFS）擴展，遇門 step+1，否則 step 不變。一旦到達 mp==2（外部區域）即返回 step。

關鍵代碼片段

void dfs(int x,int y) {
    mp[x][y]=2;
    for(int i=0;i<4;++i) {
        int dx=x+dir[i][0], dy=y+dir[i][1];
        if(isok(dx,dy) && mp[dx][dy]==0 && !door[dx][dy]) dfs(dx,dy);
    }
}

int bfs() {
    priority_queue<Node> Q;
    Q.push({sx,sy,0}); vis[sx][sy]=1;
    while(!Q.empty()) {
        Node cur=Q.top(); Q.pop();
        if(mp[cur.x][cur.y]==2) return cur.step;
        for(int i=0;i<4;++i) {
            Node nxt={cur.x+dir[i][0], cur.y+dir[i][1], cur.step};
            if(isok(nxt.x,nxt.y) && mp[nxt.x][nxt.y]!=1 && !vis[nxt.x][nxt.y]) {
                if(door[nxt.x][nxt.y]) nxt.step++;
                vis[nxt.x][nxt.y]=1; Q.push(nxt);
            }
        }
    }
    return -1;
}

邊界處理技巧

數據可能含超出 [1,199] 的座標，直接擴大數組至 2005×2005 並動態追蹤最大邊界 N,M。尼莫若在外部直接輸出 0。