ZOJ 3864 Quiz for EXO-L【BFS】【模拟】

发表于 | 更新于 | 分类于

题意：

给出数字，求出数字转化为01矩阵后代表的图案的类型。

思路：

和 UVa 1103 Ancient Messages 类似，这些图案的区别在于黑白连通块的数量不同，根据这一关系能判断出除样例外的所有图案，最后样例中的这两个图案根据根据黑块的最大团和其他团的数量关系确定。

MyCode：

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int N = 999;

typedef pair<int, int> pii;

int a[N][N];
bool vis[N][N];
double cnt[11];
int dir[][2] = {0,1,1,0,-1,0,0,-1,1,1,-1,1,1,-1,-1,-1};

int T, n, m, t, w, b;
void BFS(int x, int y, int tar)
{
    queue<pii> Q;
    Q.push({x, y});
    while(!Q.empty())
    {
        pii now = Q.front();
        Q.pop();
        for(int i = 0; i < 8; ++i)
        {
            int xx = now.first  + dir[i][0];
            int yy = now.second + dir[i][1];
            if(xx < 0 || xx >= n || yy < 0 || yy >= n)
                continue;
            if(vis[xx][yy] || a[xx][yy] != tar)
                continue;

            if(!tar) ++cnt[b];
            vis[xx][yy] = 1;
            Q.push({xx, yy});
        }
    }
}

void outmap()
{
    for(int i = 0; i < n; ++i, puts(""))
        for(int j = 0; j < n; ++j)
            cout << a[i][j];
}

void outvis()
{
    for(int i = 0; i < n; ++i, puts(""))
        for(int j = 0; j < n; ++j)
            cout << vis[i][j];
}

int main()
{
//    freopen("in.txt", "r", stdin);
    scanf("%d", &T);
    while(T--)
    {
        w = b = 0;
        int now = 1, idx = 0;
        memset(a, 0, sizeof(a));
        memset(cnt, 0, sizeof(cnt));
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &n,&m);
        while(m--)
        {
            scanf("%d", &t);
            for(int i = 0; i < t; ++i)
            {
                a[(idx + i) / n][(idx + i) % n] = now;
            }
            idx = idx + t;
            now ^= 1;
        }

        BFS(0, 0, 1);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(!vis[i][j])
                {
                    if(a[i][j] == 1)
                    {
                        BFS(i, j, 1);
                        ++w;
                    }
                    else
                    {
                        BFS(i, j, 0);
                        ++b;
                    }
                }

        if(w == 1 && b == 9)    puts("Baekhyun");
        if(w == 0 && b == 5)    puts("Chanyeol");
        if(w == 2 && b == 1)    puts("Chen");
        if(w == 1 && b == 1)    puts("D.O");
        if(w == 12&& b == 2)    puts("Kai");
        if(w == 0 && b == 3)    puts("Kris");
        if(w == 1 && b == 6)    puts("Lay");
        if(w == 7 && b == 5)    puts("Luhan");
        if(w == 7 && b == 2)    puts("Suho");
        if(w == 3 && b == 2)    puts("Tao");
        
        if(w == 1 && b == 5)
        {
            sort(cnt, cnt + 5);
            double res = (cnt[0] + cnt[1] + cnt[2] + cnt[3]) / cnt[4];
            puts(res < 0.4 ? "Sehun" : "Xiumin");
        }
    }
    return 0;
}

/***
name  w  b
Baekhyun 1 9
Chanyeol 0 5
Chen 2 1
D.O 1 1
Kai 12 2
Kris 0 3
Lay 1 6
Luhan 7 5
Sehun 1 5
Suho 7 2
Tao 3 2
Xiumin 1 5
***/
Donate comment here
0%