DFS 基本架構 -- UVa 10336

題目: http://uva.onlinejudge.org/external/103/10336.html

這是很傳統的 Flood Fill/Finding Connected Components (9/26)

經典教本 CLRS, Introduction to Algorithms 3/e 給出 recursive 版本的 DFS，

習題請你給 non-recursive 版本的 DFS。

來看程式基本資料結構：

bool visited[1000][1000];

這是最重要的部分，DFS 精神就是盡量走到底，走過的不要再走。

怎麼知道有沒有走過？就記起來唄。

接著是走的動作。Non-recursive 實作方式就是仰賴 stack。

void visit()

{

    Node node(x, y);

    std::stack<Node> dfs_stack;

    dfs_stack.push(node);

    while (dfs_stack.size() > 0)

    {

        Node top = dfs_stack.top();

        dfs_stack.pop();

        // 假如位置不合法，略過唄

        // 假如不在同一塊字母區域，也略過唄

        // 假如走過了，還是略過

        if (visited[top.x_][top.y_])

        {

            continue;

        }

        // 我走過了，記起來

        visited[top.x_][top.y_] = true;

        // 盡量走到底，有四個方位就走四個，有八個就走八個

        for (...)

        {

            Node next(...);

            dfs_stack.push(next);

        }

    }

}

int main(int argc, char* argv[])

{

    // UVa 讀入數據，沒甚麼特別的，就刻進去

    for (int case_id = 1; case_id <= num_testcases; case_id++)

    {

        // 還是讀數據

        // 初始化 visit[][]

        // 開始 DFS-Visit()，把結果記起來

        std::map<char, int> rank_map;

        for (...)

        {

            char letter = grid[i][j];

            if (!visited[i][j])

            {

                visit(i, j, letter);

                rank_map[letter]++;

            }

        }

        // 把結果排序一下印出來

    }

    return 0;

}

整個結構大致如此。

Source code: https://bitbucket.org/Menggen/uva/src/c0267d044883c6b9820e93c457f00ae8f49dcbc7/UVa/acm_10336.cc?at=master

基本上作超過 200 題，這麼麻煩的題目也要順手撿起來。