同題：UVa 10336－Rank the Languages
你可能有注意到世界上有許多地區使用英語及西班牙語。現在我們就要來對世界上所有地區使用的語言作個排行榜。
你會給一個地圖，在上面會標示各地區以幾他們所使用的語言。請看以下的地圖 (表格)：
| t | t | u | u | t | t | d | d |
| t | t | u | u | t | t | d | d |
| u | u | t | t | u | u | d | d |
| u | u | t | t | u | u | d | d |
每個字元代表一種語言，並且區域被定義為同一個字元相連的地區。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