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 |
Each character represents a language, and regions are defined as areas connected by the same character. Two characters are "connected" if they are adjacent in the up, down, left, or right directions. So, in the above map, 3 regions are speaking the language "t," 3 regions speaking the language "u," and 1 region speaking the language "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