louisfghbvc的部落格

問題描述 ：

在一張n*n大小的地圖中，從起點(1,1)到終點(n-2, n-2)的路徑，保證只會存在一條路徑，若遇到十字路口判斷時，判斷順序為下、上、左、右，陣列中的值1代表牆壁，0代表可以通過的點。

輸入說明 ：

第一個數字代表陣列大小n ( n ≤ 20 )，後續資料為地圖配置。

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1
1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1
1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1
1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1
1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1
1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1
1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

輸出說明 ：

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 # 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 # 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 # 1 1 1 1 1 * * * 1 1 1 1 0 0 0 1 1 1
1 # 1 1 1 1 1 * 1 * 1 1 1 1 0 1 0 1 1 1
1 # 1 # # # 1 * 1 * 1 1 1 1 0 1 0 1 1 1
1 # 1 # 1 # 1 * 1 * 1 1 1 1 0 1 0 1 1 1
1 # 1 # 1 # 1 * 1 * 1 1 1 0 0 1 0 1 1 1
1 # 1 # 1 # * * 1 1 1 1 1 1 1 1 0 1 1 1
1 # 1 # 1 # 1 * 1 1 1 1 1 1 1 1 0 1 1 1
1 # 1 # 1 # 1 # # # # # # # # # # 1 1 1
1 # # # 1 # # # 1 1 1 1 1 1 1 1 # 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 # # # # # 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 * 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # # # # # # # 1
1 1 1 1 1 1 1 1 1 1 1 1 * 1 1 1 * 1 # 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
井字(#)代表正確路徑，星號(*)代表經過但不是正確的路徑。

思路:

回溯法, 每個點都走走看, 如果那個點之後不能走到終點, 把那個點變星號 ,要注意順序, 下上左右, 

程式碼:

#include <iostream>

using namespace std;
int n;
int mp[25][25];
char ans[25][25];
bool over;
void dfs(int x, int y){
    if(x == n - 2 && y == n - 2){
        ans[x][y] = '#';
        over = true;
        return;
    }
    ans[x][y] = '#';
    if(x + 1 < n && ans[x + 1][y] == '0' && !over)
        dfs(x + 1, y);
    if(x - 1 >= 0 && ans[x - 1][y] == '0' && !over)
        dfs(x - 1, y);
    if(y - 1 >= 0 && ans[x][y - 1] == '0' && !over)
        dfs(x, y - 1);
    if(y + 1 < n && ans[x][y + 1] == '0' && !over)
        dfs(x, y + 1);
    if(!over)
        ans[x][y] = '*';
}
int main()
{
    while(cin >> n){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cin >> mp[i][j];
                ans[i][j] = mp[i][j] + '0';
            }
        }
        over = false;
        dfs(1, 1);
        for(int i = 0; i < n; ++i){
            cout << ans[i][0];
            for(int j = 1; j < n; ++j){
                cout << " " << ans[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}