ZeroJudge D365: 10336 - Rank the Languages

題目敘述

每個輸入第一行有一個正整數N，接下來有N筆測資，每筆測資第一行有一個H跟W，代表接下來地圖的高與寬。接下來會有一個H*W的地圖，使用字元/字串的方式來收資料。要求要算出每個字元的領地在地圖中有幾塊。按照地區的數量由小到大輸出，詳情請見範例輸出。

範例輸入

2

4 8

ttuuttdd

ttuuttdd

uuttuudd

uuttuudd

9 9

bbbbbbbbb

aaaaaaaab

bbbbbbbab

baaaaacab

bacccccab

bacbbbcab

bacccccab

baaaaaaab

bbbbbbbbb

範例輸出

World #1

t: 3

u: 3

d: 1

World #2

b: 2

a: 1

c: 1

解題思路

使用DFS來將每一個點走過一遍來確認地圖上有幾個不同字元的地區，可以用MAP的方式把字元的地區數量存起來。需要注意的是，需要有一個陣列/Vector來紀錄走過的每一個點來避免DFS重複計算的情況。輸出的時候要按照地區的數量由大到小輸出，這時可以將每一個字元和地區數量存在一個Pair裡面，第一個欄位存int，第二個欄位存字元，並把這些Pair存在陣列/Vector裡，這樣就可以用Algorithm的Sort來排序要輸出的資料，最後只要用For迴圈依序輸出即可。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

vector<string>str;
vector<vector<int>>walk;
int H, W;

void DFS(int y, int x)
{
    if (walk[y][x] == 1) return;
    else
    {
        walk[y][x] = 1;
        if (y-1 >= 0 && walk[y-1][x] == 0 && str[y-1][x] == str[y][x])
        {
            DFS(y-1, x);
        }
        if (y+1 < H && walk[y+1][x] == 0 && str[y+1][x] == str[y][x])
        {
            DFS(y+1, x);
        }
        if (x-1 >= 0 && walk[y][x-1] == 0 && str[y][x-1] == str[y][x])
        {
            DFS(y, x-1);
        }
        if (x+1 < W && walk[y][x+1] == 0 && str[y][x+1] == str[y][x])
        {
            DFS(y, x+1);
        }
    }
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        cin >> H >> W;
        str.clear();
        walk.clear();
        map<char, int>MAP;
        for (int j = 0; j<H; j++)
        {
            string tmp;
            cin >> tmp;
            str.push_back(tmp);
            vector<int>it;
            for (int k = 0; k<W; k++)
            {
                it.push_back(0);
            }
            walk.push_back(it);
        }
        vector<char>ch;
        for (int j = 0; j<H; j++)
        {
            for (int k = 0; k<W; k++)
            {
                if (walk[j][k] == 0)
                {
                    char tmp = str[j][k];
                    DFS(j, k);
                    if (MAP[tmp] == 0) ch.push_back(tmp);
                    MAP[tmp]++;
                }
            }
        }
        cout << "World #" << i+1 << endl;
        vector<pair<int, char>>ans;
        for (int j = 0; j<ch.size(); j++)
        {
            pair<int, char>tmp;
            tmp.second = ch[j];
            tmp.first = MAP[ch[j]] * -1;
            ans.push_back(tmp);
        }
        sort(ans.begin(), ans.end());
        for (int j = 0; j<ans.size(); j++)
        {
            cout << ans[j].second << ": " << ans[j].first*-1 << endl;
        }
    }
}