#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
int a,b;
};
int k,n,m,a[1005][1005],ma[2][2][2][2],used[1005][1005],otg,maa=1000000000,win[1005][1005][5];
string s;
void prec()
{
int h=0,fir=-1;
for(int i1=0;i1<=1;i1++)
{
for(int i2=0;i2<=1;i2++)
{
for(int i3=0;i3<=1;i3++)
{
for(int i4=0;i4<=1;i4++)
{
for(int j=0;j<k;j++)
{
int p=ma[i1][i2][i3][i4];
if(s[j]=='S')
{
if(i1==1)
{
h++;
ma[i1][i2][i3][i4]=max(p,h);
}
else
{
if(fir==-1)fir=h;
h=0;
}
}
if(s[j]=='W')
{
if(i2==1)
{
h++;
ma[i1][i2][i3][i4]=max(p,h);
}
else
{
if(fir==-1)fir=h;
h=0;
}
}
if(s[j]=='E')
{
if(i3==1)
{
h++;
ma[i1][i2][i3][i4]=max(p,h);
}
else
{
if(fir==-1)fir=h;
h=0;
}
}
if(s[j]=='N')
{
if(i4==1)
{
h++;
ma[i1][i2][i3][i4]=max(p,h);
}
else
{
if(fir==-1)fir=h;
h=0;
}
}
if(j==k-1&&h)
{
if(fir==-1)ma[i1][i2][i3][i4]=1000000000;
else ma[i1][i2][i3][i4]=max(ma[i1][i2][i3][i4],h+fir);
}
}
fir=-1;
h=0;
}
}
}
}
}
void check()
{
for(int i1=0;i1<=1;i1++)
{
for(int i2=0;i2<=1;i2++)
{
for(int i3=0;i3<=1;i3++)
{
for(int i4=0;i4<=1;i4++)
{
cout<<ma[i1][i2][i3][i4]<<" "<<i1<<" "<<i2<<" "<<i3<<" "<<i4<<endl;
}
}
}
}
}
int bfs(cell beg)
{
int br=1,w1,w2,w3,w4;
cell w,nb;
queue<cell>q;
used[beg.a][beg.b]=1;
q.push(beg);
while(!q.empty())
{
w=q.front();
q.pop();
nb.a=w.a-1;
nb.b=w.b;
if(nb.a>0&&!used[nb.a][nb.b])
{
win[nb.a][nb.b][1]=1;
w1=win[nb.a][nb.b][1];
w2=win[nb.a][nb.b][2];
w3=win[nb.a][nb.b][3];
w4=win[nb.a][nb.b][4];
if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
{
used[nb.a][nb.b]=1;
br++;
q.push(nb);
}
}
nb.a=w.a;
nb.b=w.b+1;
if(nb.b<=m&&!used[nb.a][nb.b])
{
win[nb.a][nb.b][2]=1;
w1=win[nb.a][nb.b][1];
w2=win[nb.a][nb.b][2];
w3=win[nb.a][nb.b][3];
w4=win[nb.a][nb.b][4];
if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
{
used[nb.a][nb.b]=1;
br++;
q.push(nb);
}
}
nb.a=w.a;
nb.b=w.b-1;
if(nb.b>0&&!used[nb.a][nb.b])
{
win[nb.a][nb.b][3]=1;
w1=win[nb.a][nb.b][1];
w2=win[nb.a][nb.b][2];
w3=win[nb.a][nb.b][3];
w4=win[nb.a][nb.b][4];
if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
{
used[nb.a][nb.b]=1;
br++;
q.push(nb);
}
}
nb.a=w.a+1;
nb.b=w.b;
if(nb.a<=n&&!used[nb.a][nb.b])
{
win[nb.a][nb.b][4]=1;
w1=win[nb.a][nb.b][1];
w2=win[nb.a][nb.b][2];
w3=win[nb.a][nb.b][3];
w4=win[nb.a][nb.b][4];
if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
{
used[nb.a][nb.b]=1;
br++;
q.push(nb);
}
}
}
return br;
}
void read()
{
cin>>k>>n>>m>>s;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]==0)used[i][j]=1;
}
}
prec();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!used[i][j])
{
cell d;
d.a=i;
d.b=j;
int f=bfs(d);
if(maa>f)
{
maa=f;
otg=1;
}
else if(maa==f)
{
otg++;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!=0)used[i][j]=0;
}
}
memset(win,0,sizeof(win));
}
}
}
cout<<maa<<endl<<otg<<endl;
}
int main()
{
speed();
read();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
231 ms |
20476 KB |
Output is correct |
| 2 |
Execution timed out |
2033 ms |
27664 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
20056 KB |
Output is correct |
| 2 |
Correct |
59 ms |
20528 KB |
Output is correct |
| 3 |
Correct |
75 ms |
20572 KB |
Output is correct |
| 4 |
Correct |
49 ms |
20572 KB |
Output is correct |
| 5 |
Correct |
21 ms |
20684 KB |
Output is correct |
| 6 |
Correct |
1228 ms |
20928 KB |
Output is correct |
| 7 |
Correct |
54 ms |
20316 KB |
Output is correct |
| 8 |
Correct |
70 ms |
20744 KB |
Output is correct |
| 9 |
Correct |
941 ms |
20600 KB |
Output is correct |
| 10 |
Correct |
55 ms |
20568 KB |
Output is correct |
| 11 |
Correct |
1152 ms |
20616 KB |
Output is correct |
| 12 |
Correct |
1170 ms |
20616 KB |
Output is correct |
| 13 |
Correct |
1103 ms |
21072 KB |
Output is correct |
| 14 |
Correct |
1109 ms |
20932 KB |
Output is correct |
| 15 |
Correct |
1167 ms |
20932 KB |
Output is correct |
| 16 |
Correct |
1132 ms |
20824 KB |
Output is correct |
| 17 |
Correct |
1088 ms |
20772 KB |
Output is correct |
| 18 |
Correct |
1120 ms |
20568 KB |
Output is correct |
| 19 |
Correct |
1020 ms |
20816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
231 ms |
20476 KB |
Output is correct |
| 2 |
Execution timed out |
2033 ms |
27664 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
