#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 805, M = 1e5 + 5, C = N * N, INF = 1e9;
const char dir[5] = "WESN";
const int dx[4] = { 0, 0, -1, 1 }, dy[4] = { 1, -1, 0, 0 };
int u[N][N], mx_seq[1 << 4], a[M], used[N][N], q[C], mask[N][N], last_us[N][N], comp[N][N], ans[N][N];
bool isSpec[N][N], isDead[C];
pair<int, int> comp_spec[C];
int st_cnt = 0, m, r, c;
int findSet(int v) {
return q[v] < 0 ? v : q[v] = findSet(q[v]);
}
int toNum(int x, int y) {
return x * c + y;
}
void connect(int a, int b) {
a = findSet(a);
b = findSet(b);
isSpec[comp_spec[a].first][comp_spec[a].second] = false;
auto spec = comp_spec[b];
if (q[a] > q[b])
swap(a, b);
isDead[a] = isDead[a] || isDead[b];
q[a] += q[b];
q[b] = a;
comp_spec[a] = spec;
comp[spec.first][spec.second] = a;
}
bool bfs(int sx, int sy) {
queue<pair<int, int>> q;
q.push({sx, sy});
used[sx][sy] = ++st_cnt;
int cur_comp = findSet(toNum(sx, sy)),
infected_count = 1;
vector<pair<int, int>> visited;
while (!q.empty()) {
pair<int, int> node = q.front();
q.pop();
visited.push_back(node);
for (int i = 0; i < 4; i++) {
int x = node.first + dx[i],
y = node.second + dy[i];
if (x >= 0 && x < r && y >= 0 && y < c &&
used[x][y] != st_cnt) {
if (last_us[x][y] != st_cnt) {
mask[x][y] = 0;
last_us[x][y] = st_cnt;
}
mask[x][y] |= 1 << i;
// cout << node.first << " " << node.second << " " << x << " " << y << "\n";
if (mx_seq[mask[x][y]] >= u[x][y]) {
int oth_comp = findSet(toNum(x, y));
if (oth_comp != cur_comp) {
connect(cur_comp, oth_comp);
return false;
}
infected_count++;
used[x][y] = st_cnt;
q.push({x, y});
}
}
}
}
for (auto p : visited) {
if (ans[p.first][p.second] < infected_count)
exit(1);
ans[p.first][p.second] = infected_count;
}
return true;
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> m >> r >> c >> s;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> u[i][j];
isSpec[i][j] = 1;
comp[i][j] = toNum(i, j);
comp_spec[comp[i][j]] = { i, j };
if (u[i][j] == 0)
u[i][j] = INF + 1;
ans[i][j] = INF;
}
}
for (char &c : s) {
c = find(dir, dir + 4, c) - dir;
}
s += s;
for (int i = 0; i < (1 << 4); i++) {
for (int j = 0; j < m + m; j++) {
a[j] = (i >> s[j]) & 1;
}
for (int j = 0, k = -1; j < m + m; j++) {
if (a[j]) {
if (j == m + m - 1 || a[j + 1] == 0)
mx_seq[i] = max(mx_seq[i], j - k);
}
else {
k = j;
}
}
if (mx_seq[i] == m + m)
mx_seq[i] = INF;
}
fill(q, q + C, -1);
bool work = true;
while (work) {
work = false;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (isSpec[i][j] && !isDead[comp[i][j]] && u[i][j] < INF) {
if (bfs(i, j))
isDead[comp[i][j]] = 1;
else
work = true;
}
}
}
// for (int x = 0; x < r; x++) {
// for (int y = 0; y < c; y++) {
// cout << findSet(toNum(x, y)) << " ";
// }
// cout << "\n";
// }
// cout << "\n";
// for (int x = 0; x < r; x++) {
// for (int y = 0; y < c; y++) {
// cout << ans[x][y] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
// for (int x = 0; x < r; x++) {
// for (int y = 0; y < c; y++) {
// cout << isDead[findSet(toNum(x, y))] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
// cout << "\n";
// cout << "\n";
}
int mn = INF, ct = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (ans[i][j] < mn) {
mn = ans[i][j];
ct = 0;
}
if (ans[i][j] == mn) {
ct++;
}
}
}
cout << mn << "\n" << ct;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
4252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
