Problem 784 Maze Exploration，迷宮探索

此題給你一個迷宮，迷宮皆用字元 'X' 圍起，而目前的位置是在字元 '*' (星號)，可以上下左右移動，要找出在這個迷宮所能走到的範圍，並且用字元 '#' 填滿這個範圍。

我們可以先建立一個陣列，題目規定範圍在寬：30、長：80。

#define ROW 33
#define COL 83
char str[ROW][COL];

接著在主程式讀取字串並且記憶字元 '*' 在陣列的位置：

for (line = 0, isStar = 0; ; line ++)
{
    gets(str[line]);
    len = strlen(str[line]);
    if (!isStar)
    {
        for (i = 0; i < len; i ++)
            if (str[line][i] == '*') 
            { startI = line, startJ = i; isStar = 1; break; }
    }
    if (str[line][0] == '_') break;
}

isStar 為判斷字元 '*' 是否出現過，startI、startJ 記錄字元 '*' 在陣列之位置，只要一讀到字元 '_' 便跳出並且計算。
接下來就是將探索地區填滿字元 '#'，其實只要用遞迴就可以解決這個問題，讀入座標，將此位置的字元改為 '#'，並且嘗試上下左右位置是否為 ' '，再將這個位置傳入遞迴。C 語言程式碼如下：

void visit(int i, int j)
{
    str[i][j] = '#';
    
    if (str[i - 1][j] == ' ') visit(i - 1, j);
    if (str[i + 1][j] == ' ') visit(i + 1, j);
    if (str[i][j - 1] == ' ') visit(i, j - 1);
    if (str[i][j + 1] == ' ') visit(i, j + 1);
}

最後只須在主程式內這麼呼叫：

visit(startI, startJ);

By David.K

p784題目連結
回ACM題庫目錄
回首頁