#include <bits/stdc++.h>
using namespace std;
#define amax(a, b) a = max(a, b)
#define cellid(r, c) (r*C+c)
#define extract(cell) (cell/C)][(cell%C)
constexpr int INF = 1e9+42;
int M, R, C;
vector<vector<int>> U;
string to_s(int cell) {
return to_string(cell/C)+","+to_string(cell%C);
}
struct patate {
int centre;
int num_cases = 1;
bool operator<(const patate& other) const {
return num_cases > other.num_cases;
}
};
struct Dir {
int v, h;
inline bool ok(int cell) {
int r = cell/C, c = cell%C;
if (0 <= r+v && r+v < R && 0 <= c+h && c+h < C && U[r+v][c+h]) {
return true;
} else {
return false;
}
}
inline int next(int cell) {
return cell+h+v*C;
}
};
const Dir DIRS[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int maxconsecutive[1<<4];
vector<int> uf;
vector<int> numchilds;
priority_queue<patate> pq;
int timer = 1;
vector<int> vu;
vector<int> bestcost;
int ans = INF;
int ansq = 0;
int root(int u) {
return uf[u] == u ? u : uf[u] = root(uf[u]);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> M >> R >> C;
string dirs;
cin >> dirs;
dirs.append(dirs);
char _map[256];
_map['S'] = 0;
_map['W'] = 1;
_map['N'] = 2;
_map['E'] = 3;
uf.resize(R*C);
vu.resize(R*C);
numchilds.assign(R*C, 1);
bestcost.assign(R*C, INF);
iota(uf.begin(), uf.end(), 0);
for (int mask = 0; mask < 1<<4; mask++) {
int l = 0;
for (char c : dirs) {
if ((mask >> _map[(unsigned char)c]) & 1) l++;
else l = 0;
maxconsecutive[mask] = max(maxconsecutive[mask], l);
}
if (maxconsecutive[mask] >= M) maxconsecutive[mask] = INF;
}
U.assign(R, vector<int>(C));
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
cin >> U[r][c];
if (U[r][c]) {
pq.push({cellid(r, c), 1});
}
}
}
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
if (root(cur.centre) != cur.centre || numchilds[cur.centre] != cur.num_cases) continue;
timer++;
queue<int> q;
q.push(cur.centre);
vu[cur.centre] = timer;
bool stopbfs = false;
int num_explore = 0;
vector<int> explored;
while (!q.empty() && !stopbfs) {
auto u = q.front(); q.pop();
explored.push_back(u);
num_explore++;
for (auto dir : DIRS) {
int next = dir.next(u);
if (dir.ok(u)) {
int i = 2;
int mask = 0;
for (auto dir2 : DIRS) {
int k = dir2.next(next);
if (dir2.ok(next) && vu[k] == vu[cur.centre]) {
mask += 1<<i;
}
i++, i &= 3;
}
if (U[extract(next)] <= maxconsecutive[mask]) {
if (vu[next] != timer && root(next) == cur.centre) {
vu[next] = timer;
q.push(next);
} else if (root(next) != cur.centre) {
uf[cur.centre] = root(next);
numchilds[root(next)] += numchilds[cur.centre];
pq.push({root(next), numchilds[root(next)]});
stopbfs = true;
break;
}
}
}
}
}
if (!stopbfs) {
ans = min(ans, num_explore);
for (auto k : explored) {
bestcost[k] = min(bestcost[k], num_explore);
}
}
}
for (int i = 0; i < R*C; i++) {
if (bestcost[i] == ans) ansq++;
}
cout << ans << '\n' << ansq << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
468 KB |
Output is correct |
2 |
Correct |
257 ms |
21212 KB |
Output is correct |
3 |
Correct |
229 ms |
21240 KB |
Output is correct |
4 |
Correct |
272 ms |
21180 KB |
Output is correct |
5 |
Correct |
171 ms |
21140 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
278 ms |
21320 KB |
Output is correct |
8 |
Correct |
65 ms |
7588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
724 KB |
Output is correct |
3 |
Correct |
5 ms |
724 KB |
Output is correct |
4 |
Correct |
5 ms |
724 KB |
Output is correct |
5 |
Correct |
7 ms |
724 KB |
Output is correct |
6 |
Correct |
5 ms |
724 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
5 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
5 ms |
724 KB |
Output is correct |
14 |
Correct |
5 ms |
724 KB |
Output is correct |
15 |
Correct |
5 ms |
648 KB |
Output is correct |
16 |
Correct |
5 ms |
724 KB |
Output is correct |
17 |
Correct |
3 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
5 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
468 KB |
Output is correct |
2 |
Correct |
257 ms |
21212 KB |
Output is correct |
3 |
Correct |
229 ms |
21240 KB |
Output is correct |
4 |
Correct |
272 ms |
21180 KB |
Output is correct |
5 |
Correct |
171 ms |
21140 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
278 ms |
21320 KB |
Output is correct |
8 |
Correct |
65 ms |
7588 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
5 ms |
724 KB |
Output is correct |
11 |
Correct |
5 ms |
724 KB |
Output is correct |
12 |
Correct |
5 ms |
724 KB |
Output is correct |
13 |
Correct |
7 ms |
724 KB |
Output is correct |
14 |
Correct |
5 ms |
724 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
5 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
5 ms |
724 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
340 KB |
Output is correct |
21 |
Correct |
5 ms |
724 KB |
Output is correct |
22 |
Correct |
5 ms |
724 KB |
Output is correct |
23 |
Correct |
5 ms |
648 KB |
Output is correct |
24 |
Correct |
5 ms |
724 KB |
Output is correct |
25 |
Correct |
3 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
5 ms |
724 KB |
Output is correct |
28 |
Correct |
274 ms |
24700 KB |
Output is correct |
29 |
Correct |
205 ms |
21348 KB |
Output is correct |
30 |
Correct |
231 ms |
21356 KB |
Output is correct |
31 |
Correct |
262 ms |
20780 KB |
Output is correct |
32 |
Correct |
241 ms |
21004 KB |
Output is correct |
33 |
Correct |
249 ms |
21192 KB |
Output is correct |
34 |
Correct |
361 ms |
24496 KB |
Output is correct |
35 |
Correct |
196 ms |
17744 KB |
Output is correct |
36 |
Correct |
286 ms |
21152 KB |
Output is correct |
37 |
Correct |
296 ms |
21172 KB |
Output is correct |
38 |
Correct |
269 ms |
24428 KB |
Output is correct |
39 |
Correct |
251 ms |
21432 KB |
Output is correct |
40 |
Correct |
267 ms |
21356 KB |
Output is correct |
41 |
Correct |
209 ms |
21268 KB |
Output is correct |
42 |
Correct |
218 ms |
19560 KB |
Output is correct |
43 |
Correct |
221 ms |
21388 KB |
Output is correct |
44 |
Correct |
65 ms |
7516 KB |
Output is correct |