ZeroJudge D365: Rank the Languages

同題:UVa 10336-Rank the Languages

你可能有注意到世界上有許多地區使用英語及西班牙語。現在我們就要來對世界上所有地區使用的語言作個排行榜。

你會給一個地圖,在上面會標示各地區以幾他們所使用的語言。請看以下的地圖 (表格):

ttuuttdd
ttuuttdd
uuttuudd
uuttuudd
我是地圖

每個字元代表一種語言,並且區域被定義為同一個字元相連的地區。2個字元”相連”指的是該2字元有上、下、左、右四個方向鄰近的關係。所以在上圖中有3個區域說 t 語言,有3個區域說 u 語言,有1個區域說 d 語言。

你的任務就是要找出地圖中每種語言被說的區域數,並且按照一定的順序輸出。

範例測資

範例輸入範例輸出
輸入的第一列有一個整數 N
代表以下有幾組測試資料
每組測試資料的第一列有 2 個整數 H 及 W
代表此地圖的高度及寬度
接下來的 H 列每列有 W 個字元
所有的字元均為小寫的英文字(a~z)
對每組測試資料
先輸出 “World #N”
N 是第幾組測試資料
接下來輸出在此地圖中每種語言被說的區域數 (請由大到小排列)
如果有2種語言區域數相同
請依英文字的順序輸出 (例如i語言要在q語言之前)
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的方式把字元的地區數量存起來。需要注意的是,需要有一個陣列來紀錄走過的每一個點來避免DFS重複計算的情況。輸出的時候要按照地區的數量由大到小輸出,這時可以將每一個字元和地區數量存在一個Pair裡面,第一個欄位存int,第二個欄位存字元,並把這些Pair存在陣列裡,這樣就可以用Sort來排序要輸出的資料,最後用For迴圈依序輸出。

範例程式碼-ZeroJudge D365: Rank the Languages

#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;
        }
    }
}

//ZeroJudge D365
//Dr. SeanXD

發佈留言