#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define id(x, y) ((x-1)*m+y-1)
#define coord(id) make_pair(id/m+1, id%m+1)
const string S = "NSWE";
const int dx[4] = {-1, 1, 0 ,0}, dy[4] = {0, 0, -1, 1};
int n, m, k, c[100100], a[808][808], p[700700], mx[16], chk[700700], chk2[808][808][4], out[700700];
vector<int> v[700700], nxt[700700], used[700700];
string s;
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
int findEdge(int x, int y, int d, int P) {
if(!a[x][y] || chk2[x][y][d]) return -1;
int B = 0;
for(int i=0;i<4;i++) {
int xx = x+dx[i], yy = y+dy[i];
if(1 <= xx && xx <= n && 1 <= yy && yy <= m && find(id(xx, yy)) == find(P)) B |= 1 << i;
}
if(mx[B] >= a[x][y]) {
chk2[x][y][d] = 1;
return id(x, y);
}
return -1;
}
void merge(int x, int y) {
if((x = find(x)) == (y = find(y))) return;
if(v[x].size() < v[y].size()) swap(v[x], v[y]);
if(nxt[x].size() < nxt[y].size()) swap(nxt[x], nxt[y]);
p[y] = x;
for(auto i : nxt[y]) nxt[x].push_back(i);
for(auto i : v[y]) {
v[x].push_back(i);
auto [X, Y] = coord(i);
for(int i=0;i<4;i++) {
auto B = findEdge(X+dx[i], Y+dy[i], i^1, x);
if(B != -1) nxt[x].push_back(B);
}
}
nxt[y].clear(), v[y].clear();
}
vector<int> st;
void dfs(int u) {
u = find(u);
if(chk[u] == 2) return;
if(chk[u] == 1) {
for(int i=int(st.size())-1;st[i]!=u;i--) merge(u, find(st[i]));
return;
}
chk[u] = 1;
st.push_back(u);
while(!nxt[u].empty()) {
int x = find(nxt[u].back()); nxt[u].pop_back();
if(x == find(u)) continue;
used[u].push_back(x), dfs(x);
}
chk[u] = 2;
st.pop_back();
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n >> m >> s;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j];
for(int i=0;i<n*m;i++) p[i] = i, v[i].push_back(i);
for(int i=0;i<k;i++) c[i] = 1 << (find(S.begin(), S.end(), s[i]) - S.begin());
for(int b=1;b<16;b++) {
for(int i=0;i<k;i++) if(c[i] & b) {
int j = (i+1)%k, cnt = 1;
while(j != i && (c[j] & b)) j = (j+1)%k, cnt++;
mx[b] = max(mx[b], cnt);
if(j <= i) break;
i = j;
}
if(mx[b] == k) mx[b] = 1e9;
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) for(int d=0;d<4;d++) {
auto B = findEdge(i+dx[d], j+dy[d], d^1, id(i, j));
if(B != -1) nxt[id(i, j)].push_back(B);
}
for(int i=0;i<n*m;i++) if(!chk[i]) dfs(i);
int cnt = 1e9, cnt2 = 0;
for(int i=0;i<n*m;i++) if(i == find(i) && a[i/m+1][i%m+1]) {
bool flag = 0;
for(auto u : v[i]) for(auto x : used[u]) if(find(u) != find(x)) flag = 1;
if(flag) continue;
if(v[i].size() < cnt) cnt = v[i].size(), cnt2 = 1;
else if(v[i].size() == cnt) cnt2++;
}
cout << cnt << "\n" << cnt * cnt2 << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |