UVa614 - Mapping the Route(DFS)

題目大意：

給予一張地圖，再給你起點與終點，我們想要你輸出透過題目規定的 DFS，畫出一張圖。
測試資料則會給予每一個節點來給定南邊或東邊的牆是否存在。

題目規定的 DFS:必須依序 西、北、東、南的方式遍地

輸出規定

• 如果是有經歷過的節點但卻不是從起點至終點的路徑時，輸出 “???”
• 沒有經歷過的節點，也不是起點到終點的路徑，輸出 “ “
• 如果是起點至終點的路徑就輸出從起點開始的第幾個節點
• 左邊的牆輸出 ‘|’，右邊的牆輸出 “—“

分析

輸出好難，他是在考你輸出八 = =。

由於這題是使用邊來判定有沒有連結，而不是透過點至點，而讓整個程式難寫許多，透過兩個陣列 graph 地圖狀態、record 從起點到終點的路徑。

幾個地方需要注意：如下

• 我們透過回推的方式判斷，假如 x,y 西邊有牆，也就代表 x,y-1 的東邊有牆，透過此方次來回推西邊或北邊是否有牆即可，以及要注意邊界問題。
• 我們都先假設我們的搜尋(record 陣列紀錄)是對的，所以當前的 record x,y = 上一個 record x,y+1，如果不對再改為 -1
• 要判斷邊界
• 輸出也要注意，他是3位為一道牆，因此如果數值位數沒有大於 3，就需要在左邊補上空白，如果是用 cout 就需要補上 set(3) << right。
• 再來需要透過 flag 來判斷是否有成功抵達終點，如果沒有成功抵達終點則起點也會是 “???”，因為他不是從起點到終點的路徑。
  function row_wall()
• 定義一個陣列 south_wall 來判斷 x,y 的南邊是否有牆，才可以在輸出時正確輸出。
• 走過，但並不是路徑的則將 record[x][y] = -1，在輸出時才可以正確知道此處為 “???”
  dfs 處每一個遞迴的下一行處，但需要先判斷 flag，來得知這路徑是否為起點到終點的路徑，不是才符合此條件

心得

這題的輸出才是最難的問題吧…，UVA 是不是認為這種類型的題目都不難因此都特地出一些很難的輸出格式來考大家的反應能力壓QQ，而且我最近在挑戰寫程式的過程中不用紙筆，發現很難、而且下次看到程式碼的時候還需要很多時間去重新理解、思考。我原先以為如果不用紙筆輔助思考會讓腦袋的印相加深，但似乎是不對的QQ。

然後英文還是需要加強，英文還是有點太爛了….。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 15
using namespace std;
int graph[MAXN][MAXN] ;
int record[MAXN][MAXN] ;
int direct[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
int south_wall[MAXN] ;
int sx , sy , N , M , ex , ey ;
int a , kase = 0 , flag = 0 ;

int isboard(int x , int y , int i ){

    if(x + direct[i][0] > N || x + direct[i][0] < 1 )
        return 0 ;
    if(y + direct[i][1] > M || y + direct[i][1] < 1 )
        return 0 ;
    //cout << x + direct[i][0] << ' ' << y + direct[i][1] << ' ' << N << ' ' << M  << '\n' ;
    return 1 ;
}

void dfs(int x , int y ){
    int ox , oy   ;
    ox = x ;
    oy = y ;
    if (x == ex && y == ey) {
        flag = 1 ;
        return ;
    }
    if(isboard(x,y,0) ){ //west
        x = ox + direct[0][0] ;
        y = oy + direct[0][1] ;
        if(record[x][y] == 0 && (graph[x][y] == 2 || graph[x][y] == 0)){
            record[x][y] = record[ox][oy] + 1 ;
            //cout << x << ' ' << y << " west" << '\n' ;
            dfs(x,y);
            if(flag) return ;
            record[x][y] = -1 ;
        }
    }
    if(isboard(x,y,1)){ //north
        x = ox + direct[1][0] ;
        y = oy + direct[1][1] ;
        if(record[x][y] == 0 && (graph[x][y] == 1 || graph[x][y] == 0)){
            record[x][y] = record[ox][oy] + 1 ;
            //cout << x << ' ' << y << " north" << '\n' ;
            dfs(x,y);
            if(flag) return ;
            record[x][y] = -1 ;
        }
    }
    if(isboard(ox,oy,2) ){//east
        x = ox + direct[2][0] ;
        y = oy + direct[2][1] ;
        if(record[x][y] == 0 && (graph[ox][oy] == 2 || graph[ox][oy] == 0)){
            record[x][y] = record[ox][oy] + 1 ;
            //cout << x << ' ' << y << " east" << '\n' ;
            dfs(x,y);
            if(flag) return ;
            record[x][y] = -1 ;
        }
    }
    if(isboard(ox,oy,3)){//south
        x = ox + direct[3][0] ;
        y = oy + direct[3][1] ;
        if(record[x][y] == 0 && (graph[ox][oy] == 1 || graph[ox][oy] == 0 )){
            record[x][y] = record[ox][oy] + 1 ;
            //cout << x << ' ' << y << " south" << '\n' ;
            dfs(x,y);
            if(flag) return ;
            record[x][y] = -1 ;
        }
    }
}

void row_wall( ){
    for(int i = 1 ; i <= M ; i++){
        cout << "+" ;
        if(south_wall[i]){
            cout << "---" ;
            south_wall[i] = 0 ;
        }
        else cout << "   " ;
    }
    cout << "+\n" ;
}


void output(){
    cout << "Maze " << ++kase << "\n\n" ;
    //cout << flag << '\n' ;
    for(int i = 0 ; i <= M ; i++) south_wall[i] = 1 ;

    if(flag == 0 ) record[sx][sy] = -1 ;
    for(int i = 1 ; i <= N ; i++){
        row_wall();
        cout << '|' ;
        //cout << M << '\n' ;
        for(int j = 1 ; j <= M ; j++){
            if(record[i][j] == -1)
                cout << "???" ;
            else if(record[i][j] > 0)
                cout << setw(3) << right << record[i][j] ;
            else cout << "   " ;

            if(j == M || graph[i][j] == 1 || graph[i][j] == 3)
                cout << "|" ;
            else cout << ' ' ;
            if(graph[i][j] == 2 || graph[i][j] == 3)
                south_wall[j] = 1 ;
        }
        cout << '\n' ;
    }
    for(int i = 0 ; i <= M ; i++) south_wall[i] = 1 ;
    row_wall();
    cout << "\n\n" ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout );
#endif // LOCAL
    while(cin >> N >> M >> sx >> sy >> ex >> ey && N){
        //cout << N << ' ' << M << ' ' << sx << ' ' << sy << '\n' ;
        for(int i = 1 ; i <= N ; i++){
            for(int j = 1 ; j <= M ; j++){
                cin >> a ;
                graph[i][j] = a ;
                record[i][j] = 0 ;
            }
        }
        flag = 0 ;
        record[sx][sy] = 1 ;
        dfs(sx,sy);
        output();
    }
    return 0;
}