#include<bits/stdc++.h>
using namespace std;
int M, R, C;
string D;
int U[802][802];
int f[2][2][2][2];
bool dead[802][802];
int color[802][802];
int ufd[656565];
int minv = 1010101010;
int ans = 0;
int Find(int a)
{
if(a==ufd[a]) return a;
return ufd[a] = Find(ufd[a]);
}
void Union(int a, int b)
{
ufd[Find(b)] = Find(a);
}
static int visv = 1;
int doBFS(int a, int b)
{
int ans = 0;
++visv;
queue<pair<int, int> > Q;
Q.emplace(make_pair(a, b));
while(!Q.empty())
{
auto[pa,pb] = Q.front(); Q.pop();
if(color[pa][pb] == visv) continue;
color[pa][pb] = visv; ++ans;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
//printf("%d %d\n", pa, pb);
for(int d=0; d<4; ++d)
{
int a = pa+dx[d], b = pb+dy[d];
if(0<=a&&a<R&&0<=b&&b<C)
{
if(U[a][b] == 0) continue;
bool N = a>0 && color[a-1][b] == visv;
bool S = a<R-1 && color[a+1][b] == visv;
bool W = b>0 && color[a][b-1] == visv;
bool E = b<C-1 && color[a][b+1] == visv;
//printf("%d %d %d %d %d %d\n", a, b, N, S, W, E);
if(f[N][S][W][E] >= U[a][b])
{
Q.emplace(a, b);
}
}
}
}
return ans;
}
void DF(vector<pair<int, int> > stables)
{
memset(color, 0, sizeof color);
for(auto [a, b]: stables)
{
int res = doBFS(a, b);
if(minv > res)
{
minv = res;
ans = 0;
}
if(minv == res) ans += res;
}
cout << minv << endl << ans <<endl;
}
void solve()
{
cout << endl;
vector<vector<pair<int, int> > > V;
for(int i=0; i<R; ++i)
for(int j=0; j<C; ++j)
{
vector<pair<int, int> > tv;
if(U[i][j] != 0)
{
tv.emplace_back(i, j);
V.push_back(tv);
}
}
vector<pair<int, int> > stables;
while(!V.empty())
{
volatile int K = V.size();
vector<bool> deads(K, false);
for(int i=0; i<K; ++i) ufd[i] = i;
for(int i=0; i<K; ++i)
{
for(auto [a, b]: V[i])
color[a][b] = i;
}
for(int c=0; c<(int)V.size(); ++c)
{
bool isdead = true;
int inflto = -1;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
for(auto [aa, bb]: V[c])
{
for(int d=0; d<4; ++d)
{
int a = aa+dx[d], b=bb+dy[d];
if(a<0||b<0||a>=R||b>=C) continue;
if(U[a][b] == 0) continue;
bool N = a>0 && !dead[a-1][b] && color[a-1][b] == c;
bool S = a<R-1 &&!dead[a+1][b] && color[a+1][b] == c;
bool W = b>0 && !dead[a][b-1] && color[a][b-1] == c;
bool E = b<C-1 && !dead[a][b+1] && color[a][b+1] == c;
if(f[N][S][W][E] >= U[a][b])
{
//U[a][b] is infected
if(dead[a][b])
{
isdead = false;
break;
}
if(color[a][b] == c) continue;
isdead=false;
inflto = color[a][b];
break;
}
}
if(!isdead) break;
}
if(isdead)
{
stables.push_back(V[c][0]);
deads[c] = true;
for(auto [a, b]: V[c]) dead[a][b] = true;
}
else
{
if(inflto == -1)
{ // dead by others
deads[c] = true;
for(auto [a, b]: V[c]) dead[a][b] = true;
}
else
{
//printf("%d %d\n", inflto, c);
Union(inflto, c);
}
}
}
for(int c=0; c<K; ++c)
{
if(deads[c]) continue;
int fc = Find(c);
if(fc == c) continue;
for(auto x: V[c]) V[fc].push_back(x);
}
vector<vector<pair<int, int> > > nv;
for(int c=0; c<K; ++c)
{
if(deads[c]) continue;
if(Find(c) == c) nv.push_back(V[c]);
}
V = nv;
}
DF(stables);
}
int main()
{
cin >> M >> R >> C;
cin >> D; D += D; D += D;
for(int i=0; i<R; ++i)
for(int j=0; j<C; ++j)
{
cin >> U[i][j];
U[i][j] = min(U[i][j], M);
}
for(int n=0; n<=1; ++n)
for(int s=0; s<=1; ++s)
for(int w=0; w<=1; ++w)
for(int e=0; e<=1; ++e)
{
int v = 0, cnt = 0;
for(char q: D)
{
if(n == 1 && q == 'N' ||
s == 1 && q == 'S' ||
w == 1 && q == 'W' ||
e == 1 && q == 'E') ++cnt;
else cnt = 0;
v = max(v, cnt);
}
f[n][s][w][e] = v;
}
solve();
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:187:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(n == 1 && q == 'N' ||
~~~~~~~^~~~~~~~~~~
virus.cpp:189:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
w == 1 && q == 'W' ||
~~~~~~~^~~~~~~~~~~
virus.cpp:190:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
e == 1 && q == 'E') ++cnt;
~~~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
3348 KB |
Output is correct |
| 2 |
Correct |
459 ms |
53516 KB |
Output is correct |
| 3 |
Correct |
485 ms |
51168 KB |
Output is correct |
| 4 |
Correct |
333 ms |
45012 KB |
Output is correct |
| 5 |
Correct |
626 ms |
58092 KB |
Output is correct |
| 6 |
Correct |
7 ms |
6008 KB |
Output is correct |
| 7 |
Correct |
470 ms |
61584 KB |
Output is correct |
| 8 |
Correct |
294 ms |
23616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 2 |
Correct |
22 ms |
3544 KB |
Output is correct |
| 3 |
Incorrect |
75 ms |
3516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
3348 KB |
Output is correct |
| 2 |
Correct |
459 ms |
53516 KB |
Output is correct |
| 3 |
Correct |
485 ms |
51168 KB |
Output is correct |
| 4 |
Correct |
333 ms |
45012 KB |
Output is correct |
| 5 |
Correct |
626 ms |
58092 KB |
Output is correct |
| 6 |
Correct |
7 ms |
6008 KB |
Output is correct |
| 7 |
Correct |
470 ms |
61584 KB |
Output is correct |
| 8 |
Correct |
294 ms |
23616 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 10 |
Correct |
22 ms |
3544 KB |
Output is correct |
| 11 |
Incorrect |
75 ms |
3516 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
