Description

You might have noticed that English and Spanish are spoken in many areas all over the world. Now it would be nice to rank all languages according to the number of states where they are spoken.

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

You’re given a map which shows the states and the languages where they are spoken. Look at the following map:

你會給一個地圖，在上面會標示各地區以幾他們所使用的語言。請看以下的地圖：

The map is read like this: Every letter stands for a language and states are defined as connected areas with the same letter. Two letters are “connected” if one is at left, at right, above or below the other one. So in the above map, there are three states where the language “t” is spoken, three where “u” is spoken and one state where people speak “d”.

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

Your job is to determine the number of states for each language and print the results in a certain order.

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

Input

The first line contains the number of test cases N. Each test case consists of a line with two numbers H and W, which are the height and the width of the map. Then follow H lines with a string of W letters. Those letters will only be lowercase letters from ‘a’ to ‘z’.

輸入的第一列有一個整數 N，代表以下有幾組測試資料。

每組測試資料的第一列有 2 個整數 H 及 W，代表此地圖的高度及寬度。

接下來的 H 列每列有 W 個字元，代表各地區使用的語言，所有的字元均為小寫的英文字（a~z）。

Output

For each test case print ‘World #n’, where n is the number of the test case. After that print a line for each language that appears in the test case, which contains the language, a colon, a space and the number of states, where that language is spoken. These lines have to be ordered decreasingly by the number of states. If two languages are spoken in the same number of states, they have to appear alphabetically, which means language ‘i’ comes before language ‘q’, for example.

對於每個測試案例，請印出「World #n」，其中 n 是該測試案例的編號。之後，為出現在該測試案例中的每種語言印出一行，該行包含語言、冒號、空格和該語言使用的地區數。這些行必須按使用該語言的地區數遞減排序。如果兩種語言使用的地區數相同，它們必須按字母順序排序，例如語言「i」應該要出現在語言「q」之前。

Sample Input 1

2
4 8
ttuuttdd
ttuuttdd
uuttuudd
uuttuudd
9 9
bbbbbbbbb
aaaaaaaab
bbbbbbbab
baaaaacab
bacccccab
bacbbbcab
bacccccab
baaaaaaab
bbbbbbbbb

Sample Output 1

World #1
t: 3
u: 3
d: 1
World #2
b: 2
a: 1
c: 1

Hint

先建一張地圖，0代表未走訪，1代表已走訪；目前走到的是 0 時使用遞迴向四周檢查。

method: use DFS

#include<stdio.h>
#include<stdbool.h>

// Structure to represent coordinates
struct Coordinate {
    int x;
    int y;
};

// Array representing directions: left, up, right, down
int direct[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };

// Function to compare two languages based on their territories and alphabetic order
bool order(char, int, char, int);

int main() {
    char langMap[101][101]; // Language map

    // T: number of test cases, H: map height, W: map width
    int T, H, W;

    scanf("%d", &T); // Input number of test cases

    // Analyze each test case
    for(int count=1; count<=T; count++) {
        // mark[i][j] is 1 if the region is processed, 0 otherwise
        bool mark[101][101] = {0};

        scanf("%d %d", &H, &W); // Input height and width of the 2D map

        for(int i=0; i<H; i++) // Input contents of the 2D map
            scanf("%s", langMap[i]);

        struct Coordinate coord[10000];
        int num[26] = {0}; // Array to store the count of each language

        // Perform DFS for each grid in the map
        for(int i=0; i<H; i++)
            for(int j=0; j<W; j++) {
                if(!mark[i][j]) {// Not yet processed
                    char find = langMap[i][j]; // Language in this grid
                    num[find - 'a']++; // Increment count for this language
                    int top=0, tail=0;
                    coord[top].x = i;
                    coord[top].y = j;
                    top++;
                    mark[i][j] = true; // Mark as processed

                    // DFS starts
                    while(top > tail) {
                        for(int s=0; s<4; s++) {// Four directions
                            int fx = coord[tail].x + direct[s][0];
                            int fy = coord[tail].y + direct[s][1];
                            // Explore this grid if not out of range, unprocessed, and matches the language
                            if(fx > -1 && fx < H && fy > -1 && fy < W && !mark[fx][fy] && langMap[fx][fy] == find) {
                                // Mark as processed
                                mark[fx][fy] = true;
                                coord[top].x = fx;
                                coord[top].y = fy;
                                top++;
                            }
                        }
                        tail++;
                    }
                }
            }

        char lan[26]; // Array to store languages
        int field[26]; // Array to store territory count for each language
        int c=0;
        for(int i=0; i<26; i++)
            if(num[i] > 0) {
                lan[c] = i+'a'; // Language
                field[c] = num[i]; // Territory count
                c++;
            }

        // Sort languages based on territory count and alphabetic order
        for(int i=0; i<c; i++) {
            for(int j=i+1; j<c; j++) {
                if(order(lan[i], field[i], lan[j], field[j])) {
                    char temp = lan[i];
                    lan[i] = lan[j];
                    lan[j] = temp;

                    int temp_field = field[i];
                    field[i] = field[j];
                    field[j] = temp_field;
                }
            }
        }

        printf("World #%d\\n", count);
        // Output the territories for each language
        for(int i=c-1; i>-1; i--)
            printf("%c: %d\\n", lan[i], field[i]);
    }
}

// Function to compare two languages based on their territories and alphabetic order
bool order(char ac, int a, char bc, int b) {
    if(a == b)
        return bc > ac;
    if(a > b)
        return true;
    else
        return false;
}