GrD Programming 瓦哈,在汪洋資訊中漂流,我是懶惰的,自由的!

0愛的鼓勵 0訂閱站台

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

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

ttuuttdd 
ttuuttdd 
uuttuudd 
uuttuudd  

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

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

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

BFS或DFS或集合或 ? ? ?

Lucky 貓 翻譯

測資可能會有誤，或者是太簡單...

Uva 10336 (管理：morris1028)

--------------------------------------------------------------------------------
拆題:Flooding 淹水 or BFS or DFS
我既不會bfs也不會dfs..... (喵啊!!圖論!!)
所以就把這題淹了.

另外最後的輸出方式可能不是最快的輸出,因為要round很多次 (maxi最高多少就要跑多少趟 :P)

--------------------------------------------------------------------------------

(**********************************************************************************)
(*  Problem: d365 "10336 - Rank the Languages" from Uva 10336                     *)
(*  Language: PASCAL                                                              *)
(*  Result: AC (38ms, 2568KB) on ZeroJudge                                        *)
(*  Author: grd at 2011-07-29 15:17:05                                            *)
(**********************************************************************************)


program languages;

const max=1001;
type  arraytype=array[0..max,0..max]of integer;

var map:arraytype;
    num:array[97..122]of longint;
    temp:char;
    h,w,check:longint;
    row,col,run,time:longint;

procedure flood(x,y:longint);              //flooding main
begin
        if ((x<1)or(x>h))or((y<1)or(y>w)) then exit;    //判斷退出,沒判定好不是out of range 就是
        if map[x][y]=0 then exit;                              // runtime error =_ =  | 淹水時記得牆的範圍
        if map[x][y]<>check then exit;                      // 判斷是不是同一個區域
                                                                      
        map[x][y]:=0;                                         

        flood(x+1,y);                                              //上下左右在淹一次
        flood(x-1,y);
        flood(x,y+1);
        flood(x,y-1);
end;

begin
        readln(time);
        for time:=1 to time do begin
                readln(h,w);
                fillchar(map,sizeof(map),0);
                fillchar(num,sizeof(num),0);

                for row:=1 to h do begin                           //用read務必要記得readln; 要不然會出亂子
                        for col:=1 to w do begin
                                read(temp);
                                map[row][col]:=ord(temp);
                        end;
                        readln;                                          // ^
                end;

                for row:=1 to h do
                        for col:=1 to w do begin
                                if map[row][col]>0 then begin
                                        check:=map[row][col];        //標記區塊
                                        //if check=0 then continue;
                                        inc(num[check]);              
                                        flood(row,col);
                                end;
                        end;
                for run:=97 to 122 do if num[run]>check then check:=num[run];

                writeln('World #',time);

                while check<>0 do begin          //來亂的輸出方式,找到maxi值後,從maxi 每次 maxi--
                        for run:=97 to 122 do     //然後從頭到尾搜有沒有字是跟值一樣的,一樣的就輸出........
                                if num[run]=check then writeln(chr(run),': ',num[run]);
                        dec(check);
                end;

        end;
end.

------------

水題群! (不...是flooding 題): D365,Q10336  D165  D626