11006:Rank the Languages

Time Limit: 2 sec

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.

Problem

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

ttuuttdd

ttuuttdd

uuttuudd

uuttuudd

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”.

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”.

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.

Sample Input

2

4 8

ttuuttdd

ttuuttdd

uuttuudd

uuttuudd

9 9

bbbbbbbbb

aaaaaaaab

bbbbbbbab

baaaaacab

bacccccab

bacbbbcab

bacccccab

baaaaaaab

bbbbbbbbb

Sample Output

World #1

t: 3

u: 3

d: 1

World #2

b: 2

a: 1

c: 1

————————————————

先用一個二維的map陣列把字母給load進來

然後設計一個DFS的遞迴函數，不斷往外擴張一樣字母的區域

用check_map陣列 =1 表示已經搜尋過

設計一個ASCII[255]的陣列，如果陣列index就是字母的ASCII

對應的值就是出現的區塊數。

#include<stdio.h> #include<string.h> char map[1000][1000] = {0}; int check_map[1000][1000] = {0}; void DFS( int number, int x, int y ) { check_map[y][x] = 1; if( map[y][x+1] == number && !check_map[y][x+1] ) DFS( number, x+1, y ); if( map[y][x-1] == number && !check_map[y][x-1] ) DFS( number, x-1, y ); if( map[y+1][x] == number && !check_map[y+1][x] ) DFS( number, x, y+1 ); if( map[y-1][x] == number && !check_map[y-1][x] ) DFS( number, x, y-1 ); } int main() { int Case; while( scanf( "%d", &Case ) != EOF ) { int H, W; int i; char s[1000] = {0}; char max_letter = 0; for( i = 1 ; i <= Case ; i++ ) { scanf( "%d%d", &H, &W ); int j, k; for( j = 1 ; j <= H ; j++ ) { scanf( "%s", s ); //讀一整條 for( k = 0 ; k < W ; k++) { map[j][k+1] = s[k]; check_map[j][k+1] = 0; max_letter = ( s[k] > max_letter )? s[k] : max_letter; } } int ASCII[256] = {0}, max_group_nu = 0; for( j = 1 ; j <= H ; j++ ) for( k = 1 ; k <= W ; k++ ) if( !check_map[j][k] ) { DFS( map[j][k], k, j ); ASCII[map[j][k]]++; max_group_nu = ( ASCII[map[j][k]] > max_group_nu )? ASCII[map[j][k]] : max_group_nu; } printf( "World #%d\n", i ); for( j = max_group_nu ; j >= 1 ; j-- ) //從最大group開始掃 for( k = 0 ; k <= max_letter ; k++ ) //再從a掃到z if( j == ASCII[k] ) printf( "%c: %d\n", k, j ); } } return 0; }