[SWEA] 7733 치즈 도둑

Time Lapse :20min 0sec

7733.cpp

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
#include <stdio.h>
#include <memory.h>
#include <queue>

#define gc() getchar_unlocked()
#define pc(x) putchar_unlocked(x)
#define ADD3(a, b) ((a<<3)+(a<<1)+(b))
#define REP(i, a, b) for(i = a; i < b; i++)
#define INRANGE(a,b,N) (((0)<=(a))&&((a)<(N))&&((0)<=(b))&&((b)<(N))) ? (1) : (0)
using namespace std;
int answer, N, day, block, nx, ny, cx, cy;
bool v[101], visit[100][100];
int freg[100][100];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
queue<pair<int, int>> q;

int fRI() {
int N = gc(), r = 0;
for (; 0x30 > N || N > 0x3A; N = gc());
do {
r = ADD3(r, N & 0b1111);
N = gc();
} while (0x30 <= N && N <= 0x3A);
return r;
}

void fWI(int tc) {
int r = 0, c = 0;
while (!(tc % 10)) {
c++;
tc /= 10;
}
while (tc) {
r = ADD3(r, tc % 10);
tc /= 10;
}
while (r) {
pc(r % 10 + 48);
r /= 10;
}
while (c--) pc(0x30);
return;
}

void simulation() {
register int i, j, k;
REP(day, 1, 100) {
if (!v[day]) continue;
v[day] = false;
block = 0;
memset(visit, false, sizeof(visit));
REP(i, 0, N)REP(j, 0, N) {
if (freg[i][j] >= day && !visit[i][j]) {
q.emplace(i, j);
visit[i][j] = true;
block++;
while (!q.empty()) {
cx = q.front().second;
cy = q.front().first;
q.pop();
REP(k, 0, 4) {
nx = cx + dx[k];
ny = cy + dy[k];
if (INRANGE(nx,ny,N)) {
if (!visit[ny][nx] && freg[ny][nx] >= day) {
q.emplace(ny, nx);
visit[ny][nx] = true;
}
}
}
}
}
}
answer = block > answer ? block : answer;
}
}

int main(void) {
register int tc = 1, T = fRI(), i, j;
memset(freg, 0, sizeof(freg));
memset(v, 0, sizeof(v));
while (T--) {
N = fRI();
answer = 1;
REP(i, 0, N)REP(j, 0, N) {
freg[i][j] = fRI();
v[freg[i][j]] = true;
}
simulation();
pc('#');fWI(tc++);pc(' ');fWI(answer);pc('\n');
}
return 0;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/08/04/PS/SWEA/7733/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.