This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
t=0; char ch=getchar(); int f=1;
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
if (t<0) { putchar('-'); write(-t); return; }
if (t>9) write(t/10);
putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
const int INF=1e9;
const int maxn=810;
char s[200010];
int len,n,m,d[maxn][maxn];
int mx[16],dy[300];
int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool vis[maxn][maxn];
int msk[maxn][maxn];
pair<int,int> q[maxn*maxn];
int hd,tl;
int calc(int x,int y) {
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) msk[i][j]=vis[i][j]=0;
q[hd=tl=1]=MP(x,y); vis[x][y]=1;
while (hd<=tl) {
x=q[hd].first,y=q[hd].second,hd++;
for (int i=0;i<4;i++) {
int a=x+fx[i][0],b=y+fx[i][1];
if (1<=a&&a<=n&&1<=b&&b<=m&&!vis[a][b]&&d[a][b]) {
msk[a][b]|=(1<<((i+2)%4));
if (mx[msk[a][b]]>=d[a][b]) q[++tl]=MP(a,b),vis[a][b]=1;
}
}
}
return tl;
}
int main() {
scanf("%d %d %d %s",&len,&n,&m,s+1);
dy['W']=3,dy['N']=0,dy['E']=1,dy['S']=2;
int all=0;
for (int i=1;i<=len;i++) s[i+len]=s[i],all|=(1<<dy[s[i]]);
for (int t=0;t<16;t++) {
if ((t&all)==all) { mx[t]=INF; continue; }
int cnt=0;
for (int i=1;i<=len*2;i++) {
if (t>>dy[s[i]]&1) cnt++,mx[t]=max(mx[t],cnt); else cnt=0;
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) read(d[i][j]);
int mn=INF,cnt=0;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (d[i][j]) {
int res=calc(i,j);
if (res<mn) mn=res,cnt=1; else if (res==mn) cnt++;
}
printf("%d\n%d\n",mn,cnt);
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Integer overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/
Compilation message (stderr)
virus.cpp: In function 'int main()':
virus.cpp:45:56: warning: array subscript has type 'char' [-Wchar-subscripts]
45 | for (int i=1;i<=len;i++) s[i+len]=s[i],all|=(1<<dy[s[i]]);
| ~~~^
virus.cpp:50:17: warning: array subscript has type 'char' [-Wchar-subscripts]
50 | if (t>>dy[s[i]]&1) cnt++,mx[t]=max(mx[t],cnt); else cnt=0;
| ~~~^
virus.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d %d %d %s",&len,&n,&m,s+1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |