d365: 10336 - Rank the Languages

https://zerojudge.tw/ShowProblem?problemid=d365

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

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

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

解題提示

如何從一個點擴散出去，搜尋四面八方的地圖，這項技能你已經學會了，那在這邊該如何使用呢?簡單的說就是對地圖中的每一格進行DFS搜尋，先記錄起始點的字元，假如說起始點是a，那接下來碰到的字元只要不是a都視為牆壁。拜訪過的地圖也記得做標記。

解答

#include<iostream>
using namespace std;

struct Coordinate{
    int x;
    int y;
};

int direct[4][2] = { 0,-1,
                    -1, 0,
                     0, 1,
                     1, 0};

bool order(char,int,char,int);

int main()
{
    char langMap[101][101]; //語言地圖

    //T:測資數量，H:地圖高度，W:地圖寬度
    int T,H,W;

    cin>>T; //輸入測資數量

    //對每組測資進行分析
    for(int count=1;count<=T;count++)
    {
        //mark的值為1代表已經處理的區域，0代表未處理，預設都為0
        bool mark[101][101]={0};

        cin>>H>>W; //輸入二維地圖的長寬

        for(int i=0;i<H;i++) //輸入二維地圖的內容
            cin>>langMap[i];

        Coordinate coord[10000];
        int num[26] = {0};

        //對地圖中的每一格進行DFS處理
        for(int i=0; i<H; i++)
            for(int j=0; j<W; j++)
            {
                if(!mark[i][j])//尚未被計算過
                {
                    char find = langMap[i][j]; //此格地圖為哪個字元
                    num[find - 'a']++; //將該字元出現過的數量+1
                    int top=0, tail=0;
                    coord[top].x = i;
                    coord[top].y = j;
                    top++;
                    mark[i][j] = true; //被處理過

                    //DFS搜尋開始
                    while(top>tail)
                    {

                        for(int s=0; s<4; s++)//s代表4個方向
                        {
                            int fx = coord[tail].x+direct[s][0];
                            int fy = coord[tail].y+direct[s][1];
                            //探索的這格地圖
                            //如果 沒超出地圖範圍 且 是沒被計算過的 且 跟我們想找的符號是一樣的
                            if(fx>-1&&fx<H&&fy>-1&&fy<W && !mark[fx][fy]&&langMap[fx][fy]==find)
                            {
                                //就處理把這格地圖
                                mark[fx][fy] = true;
                                coord[top].x = fx;
                                coord[top].y = fy;
                                top++;
                            }
                        }
                        tail++;
                    }

                }

                /*
                //每處理一個區塊，就印出已處理過的區域
                cout<<"("<<i<<","<<j<<")"<<endl;
                for(int o=0;o<H;o++)
                {
                    for(int p=0;p<W;p++)
                    {
                        cout<<mark[o][p];
                    }
                    cout<<endl;
                }
                */

            }

        char lan[26];
        int field[26];
        int c=0;
        for(int i=0; i<26; i++)
            if(num[i]>0)
            {
                lan[c] = i+'a'; //字元
                field[c] = num[i]; //字元區域的數量
                c++;
            }

        //排序答案順序，區外數越多的越前面，區塊數一樣多的時候，字母排序前面的調到前面
        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]))
                {
                    swap(lan[i],lan[j]);
                    swap(field[i],field[j]);
                }
            }
        }

        cout<<"World #"<<count<<endl;
        for(int i=c-1; i>-1; i--)
            cout<<lan[i]<<": "<<field[i]<<endl;

    }
}

bool order(char ac,int a,char bc,int b)
{
    if(a==b)
        return bc>ac;
    if(a>b)
        return true;
    else
        return false;
}