#include <bits/stdc++.h>
using namespace std;
int n,m,virus[805][805],nr,val[305],a[805][805],i;
char ch;
void reseteaza()
{
int i,j;
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
virus[i][j]=0;
}
}
}
int dirl[4],dirc[4],v[100005],j,ok[100005],nr1,rasp[100005],numar;
bool interior (int x,int y)
{
if (1<=x&&x<=n&&1<=y&&y<=m)
{
return 1;
}
return 0;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>nr>>n>>m;
val['S']=0;
dirl[0]=1;
dirc[0]=0;
val['N']=1;
dirl[1]=-1;
dirc[1]=0;
val['W']=2;
dirl[2]=0;
dirc[2]=-1;
val['E']=3;
dirl[3]=0;
dirc[3]=1;
for (i=1; i<=nr; i++)
{
cin>>ch;
v[i]=val[ch];
}
for (i=nr+1;i<=2*nr;i++)
{
v[i]=v[i-nr];
}
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
cin>>a[i][j];
}
}
for (i=0; i<16; i++)
{
for (j=0; j<4; j++)
{
ok[j]=0;
if ((i&(1<<j)))
{
ok[j]=1;
}
}
nr1=0;
for (j=1; j<=2*nr; j++)
{
if (ok[v[j]]==1)
{
nr1++;
rasp[i]=max(rasp[i],nr1);
}
else
{
nr1=0;
}
}
}
int minim=1000005,nrfin=0;
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
if (a[i][j]==0)
{
continue;
}
reseteaza();
queue <pair <int,int> > q;
q.push({i,j});
virus[i][j]=1;
numar=1;
while (!q.empty())
{
auto acum=q.front();
q.pop();
if (virus[acum.first][acum.second]==0&&a[acum.first][acum.second]!=0)
{
for (int t=0; t<16; t++)
{
if (rasp[t]>=a[acum.first][acum.second])
{
int ok1=1;
for (int k=0; k<4; k++)
{
if ((t&(1<<k)))
{
int x,y;
x=acum.first+dirl[k];
y=acum.second+dirc[k];
if (interior(x,y)==0)
{
ok1=0;
break;
}
if (virus[x][y]==0)
{
ok1=0;
}
}
}
if (ok1==1)
{
virus[acum.first][acum.second]=1;
numar++;
break;
}
}
}
if (virus[acum.first][acum.second]==1)
{
for (int k=0;k<4;k++)
{
int x,y;
x=acum.first+dirl[k];
y=acum.second+dirc[k];
if (interior(x,y)!=0&&virus[x][y]==0)
{
q.push({x,y});
}
}
}
}
else
if (virus[acum.first][acum.second]==1)
{
for (int k=0;k<4;k++)
{
int x,y;
x=acum.first+dirl[k];
y=acum.second+dirc[k];
if (interior(x,y)!=0&&virus[x][y]==0)
{
q.push({x,y});
}
}
}
}
if (numar<minim)
{
minim=numar;
nrfin=1;
}
else
if (numar==minim)
{
nrfin++;
}
}
}
cout<<minim<<'\n'<<nrfin;
return 0;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:50:18: warning: array subscript has type 'char' [-Wchar-subscripts]
50 | v[i]=val[ch];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
