Problem Solving►UVa

UVa 10336 - Rank the Languages

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

給一張地圖，上面標示每種語言的使用區塊，兩區塊如果上下左右是同樣的語言，為同一地區。
計算某一語言有多少地區使用。

Solution

DFS 一次填一個地區，並對各語言計數。

Code

UVa 10336
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <algorithm>
#include <utility>
#include <stack>
#include <cstring>
#define N 500
using namespace std;

int main()
{
    const int dir[4][2] = { {0, -1}, {-1, 0}, {1, 0}, {0, 1} };
    int T;
    char grid[N][N];
    bool visited[N][N] = {};
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t)
    {
        int H, W;
        char tmp[N];
        scanf("%d%d ", &H, &W);
        for (int i = 1; i <= H; ++i)
        {
            fgets(tmp, N, stdin);
            for (int j = 1; j <= W; ++j)
                grid[i][j] = tmp[j - 1];
        }

        pair<char, int> lang[26];
        for (int i = 0; i < 26; ++i)
            lang[i] = make_pair('a' + i, 0);

        //DFS
        stack<pair<int, int>> S;
        char ch;
        for (int i = 1; i <= H; ++i)
            for (int j = 1; j <= W; ++j)
            {
                if (visited[i][j])
                    continue;

                S.emplace(i, j);
                ch = grid[i][j];
                visited[i][j] = true;

                while (!S.empty())
                {
                    int r = S.top().first, c = S.top().second;
                    S.pop();
                    for (int i = 0; i < 4; ++i)
                    {
                        int rr = r + dir[i][0], cc = c + dir[i][1];
                        if (rr && rr <= H && cc && cc <= W && !visited[rr][cc] && grid[rr][cc] == ch)
                        {
                            visited[rr][cc] = true;
                            S.emplace(rr, cc);
                        }
                    }
                }

                //使用該語言的區域增加
                lang[ch - 'a'].second++;
            }

        sort(lang, lang + 26, [](const pair<char,int> &a, const pair<char,int> &b) -> bool {
            return (a.second > b.second || (a.second == b.second && a.first < b.first));
        });

        printf("World #%d\n", t);
        for (int i = 0; i < 26; ++i)
        {
            if (lang[i].second)
                printf("%c: %d\n", lang[i].first, lang[i].second);
            else
                break;
        }

        //init
        for (int i = 0; i <= H; ++i)
            memset(visited[i], false, sizeof visited[i]);
    }

    return 0;
}