louisfghbvc的部落格

題目描述 : 
傳說中的勇者受到村民的委託，要去消滅地下城裡的大魔王。地下城是魔王軍的大本營，有著複雜的地道和許多怪物守衛著。大魔王接到情報，知道勇者要來找麻煩，可是大魔王昨天晚上吃壞了肚子，沒有體力氣和勇者戰鬥，所以大魔王決定要躲在勇者最不可能找到的地方，讓地下城的怪物去收拾那個囂張的勇者。 
可是地下城太大太複雜了，大魔王不知道該躲在哪才是最安全的地方，但是大魔王知道一個情報：就是勇者在碰到岔路時，一定會按照一個規則走 。請幫忙大魔王找到藏身處，讓勇者要花最多的時間才能找到大魔王。

輸入說明 : 
第一行是一個數字 n ( n < 50 )，代表這個地下城是 n*n 的正方形。迷宮接下來 n 行是由 0 和 1 的組合而成， 1 代表可走的路， 0 代表牆壁。 1 的周圍一定會至少存在一個 1 。第一行會有一個 S 代表勇者的起始位置。 ( 注意 : 1 的周圍一定會至少存在一個 1 。 )

輸出說明 : 
第一行是一個數字 n ，代表這個地下城是 n*n 的正方形迷宮。接下來 n 行是由 0 和 1 組合而成， 1 代表路， 0 代表牆壁，其中一個 1 會以 # 取代，表示大魔王的位置。 

注意 1: 每次碰到岔路時，勇者選擇路徑的順序是按照這個地圖的 1. 左 , 2. 右 , 3. 下 , 4. 上。如果選走左邊，在走完整個左邊的路徑後，才會回到這個岔路，再選另一條路。

注意 2: 上面提到的周圍是代表上下左右，勇士沒辦法斜著走，例如下圖： 
11S0
1001
1001
1111 
勇士一定要繞一圈才會找到大魔王。

範例 :

思路:

回溯法, 從起點走, 紀錄誰最晚出去遞迴則是魔王的位置, 走完那個點記得要標記不能走,回來那個點在取消標記

程式碼:

#include <iostream>

using namespace std;
char mp[55][55];
int n, mx, my;
void dfs(int x, int y){
    mx = x;
    my = y;
    mp[x][y] = '0';
    if(y - 1 >= 0 && mp[x][y - 1] == '1'){
        dfs(x, y - 1);
    }
    if(y + 1 < n && mp[x][y + 1] == '1'){
        dfs(x, y + 1);
    }
    if(x + 1 < n && mp[x + 1][y] == '1'){
        dfs(x + 1, y);
    }
    if(x - 1 >= 0 && mp[x - 1][y] == '1'){
        dfs(x - 1, y);
    }
    mp[x][y] = '1';
}
int main()
{

    while(cin >> n){
        int x, y;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cin >> mp[i][j];
                if(mp[i][j] == 'S'){
                    x = i;
                    y = j;
                }
            }
        }
        dfs(x, y);
        mp[x][y] = 'S';
        mp[mx][my] = '#';
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cout << mp[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}