UVa 10336－Rank the Languages
You might have noticed that many regions around the world use English and Spanish. Now, we're going to create a ranking of the languages used in all regions around the world.
You will be given a map indicating the number of languages spoken in each region. Please see the following map (table):
| 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 語言。
Your task is to find out the number of regions where each language is spoken on the map, and then output them in a certain order.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line of the input contains an integer N, representing the number of sets of test data. Each set of test data starts with a line containing 2 integers H and W, representing the height and width of the map respectively. The following H lines each contain W characters. All characters are lowercase English letters (a-z). | For each test case:
1. First, output “World #N”, where N is the test case number. 2. Next, output the number of regions where each language is spoken on the map (sorted in descending order). 3. If two languages have the same number of regions, output them in alphabetical order (e.g., the language “i” should appear before “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 |
Thought Process
Use DFS to traverse each point on the map to determine how many distinct regions of characters exist. A map can be used to store the number of regions for each character. To avoid redundant calculations, an array should be maintained to keep track of the visited points. When outputting the results, they should be sorted in descending order by the number of regions. To achieve this, store each character and its corresponding region count in a Pair, where the first field is the integer (region count) and the second field is the character. Store these pairs in an array and use Sort to arrange the output. Finally, iterate through the sorted array using a for loop to print the results.
Sample Code－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