#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int m,r,c;
string s;
int best[(1<<4)];
bool visited[1000][1000];
int u[1000][1000];
int dir(char c){
if(c=='N')return 0;
if(c=='S')return 1;
if(c=='E')return 2;
if(c=='W')return 3;
}
int resp(int x, int y){
int msk=0;
if(x>0 && visited[x-1][y]){
msk+=1;
}
if(x<r-1 && visited[x+1][y]){
msk+=2;
}
if(y<c-1 && visited[x][y+1]){
msk+=4;
}
if(y>0 && visited[x][y-1]){
msk+=8;
}
return msk;
}
void DFS(int x,int y){
//cout<<x<<" "<<y<<endl;
visited[x][y]=true;
if(x>0 && !visited[x-1][y]){
int msk=resp(x-1,y);
if(best[msk]>=u[x-1][y] && u[x-1][y]!=0){
DFS(x-1,y);
}
}
if(x<r-1 && !visited[x+1][y]){
int msk=resp(x+1,y);
if(best[msk]>=u[x+1][y] && u[x+1][y]!=0){
DFS(x+1,y);
}
}
if(y>0 && !visited[x][y-1]){
int msk=resp(x,y-1);
if(best[msk]>=u[x][y-1] && u[x][y-1]!=0){
DFS(x,y-1);
}
}
if(y<c-1 && !visited[x][y+1]){
int msk=resp(x,y+1);
if(best[msk]>=u[x][y+1] && u[x][y+1]!=0){
DFS(x,y+1);
}
}
}
int main(){
cin>>m>>r>>c;
cin>>s;
while(s.size()<200000){
s=s+s;
}
//cout<<s<<endl;
rep(i,0,4){
best[i]=0;
}
rep(msk,0,16){
int sz=0;
best[msk]=0;
rep(i,0,s.size()){
if(((1<<(dir(s[i])))&msk)>0){
sz++;
}else sz=0;
best[msk]=max(best[msk],sz);
}
}
rep(i,0,r){
rep(j,0,c){
cin>>u[i][j];
}
}
if(true){
lld ans1,ans2;
ans1=1000000000;
ans2=0;
//rep(i,0,16)cout<<best[i]<<endl;
rep(i,0,r){
int edge[c];
rep(j,1,c){
edge[j-1]=0;
if(u[i][j]!=0 && u[i][j-1]!=0){
if(best[4]>=u[i][j-1]){
edge[j-1]++;
}
if(best[8]>=u[i][j]){
edge[j-1]+=2;
}
}
//cout<<edge[j-1]<<" ";
}//cout<<endl;
vector<int> sizes;
vector<int> edges;
sizes.push_back(1);
rep(j,0,c-1){
if(edge[j]==3){
sizes[sizes.size()-1]++;
}else{
sizes.push_back(1);
edges.push_back(edge[j]);
}
}
int answers[sizes.size()];
rep(j,0,sizes.size()){
answers[j]=sizes[j];
if(j>0 && edges[j-1]==1){
answers[j]+=answers[j-1];
}
if(j<sizes.size()-1 && edges[j]==2){
int ptr=j;
while(ptr<edges.size() && edges[ptr]==2){
ptr++;
}
answers[ptr]=sizes[ptr];
for(int k=ptr-1;k>j;k--){
answers[k]=answers[k+1]+sizes[k];
}
answers[j]+=answers[j+1];
j=ptr;
}
}
/*rep(j,0,sizes.size()){
cout<<answers[j]<<" ";
}cout<<endl;
rep(j,0,edges.size()){
cout<<edges[j]<<" ";
}cout<<endl;*/
int ptr=0;
rep(j,0,sizes.size()){
if(u[i][ptr]!=0){
if(ans1>answers[j]){
ans1=answers[j];
ans2=0;
}
if(ans1==answers[j])ans2+=sizes[j];
}
ptr+=sizes[i];
}
}
cout<<ans1<<endl<<ans2<<endl;
return 0;
}
/*rep(i,0,16)cout<<best[i]<<" ";
cout<<endl;*/
/*rep(i,0,10)cout<<chain[i]<<","<<s[i]<<" ";
cout<<endl;
rep(i,0,4)cout<<best[i]<<" ";
cout<<endl;*/
int U[r*c];
lld ans1,ans2;
ans1=1000000000;
ans2=0;
rep(i,0,r){
rep(j,0,c){
rep(k,0,r){
rep(l,0,c){
visited[k][l]=false;
}
}
if(u[i][j]>0){
DFS(i,j);
lld can=0;
rep(k,0,r){
rep(l,0,c){
can+=visited[k][l];
}
}
if(can<ans1){
ans1=can;
ans2=0;
}
if(can==ans1)ans2++;
//cout<<can<<" "<<i<<" "<<j<<endl;
}
}
}//cout<<endl;
cout<<ans1<<endl<<ans2<<endl;
//DFS(2,0);
return 0;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i=a;i<b;i++)
virus.cpp:77:9:
rep(i,0,s.size()){
~~~~~~~~~~~~
virus.cpp:77:5: note: in expansion of macro 'rep'
rep(i,0,s.size()){
^~~
virus.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i=a;i<b;i++)
virus.cpp:122:11:
rep(j,0,sizes.size()){
~~~~~~~~~~~~~~~~
virus.cpp:122:7: note: in expansion of macro 'rep'
rep(j,0,sizes.size()){
^~~
virus.cpp:127:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j<sizes.size()-1 && edges[j]==2){
~^~~~~~~~~~~~~~~
virus.cpp:129:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<edges.size() && edges[ptr]==2){
~~~^~~~~~~~~~~~~
virus.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i=a;i<b;i++)
virus.cpp:147:11:
rep(j,0,sizes.size()){
~~~~~~~~~~~~~~~~
virus.cpp:147:7: note: in expansion of macro 'rep'
rep(j,0,sizes.size()){
^~~
virus.cpp:167:7: warning: unused variable 'U' [-Wunused-variable]
int U[r*c];
^
virus.cpp: In function 'int dir(char)':
virus.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
792 KB |
Output is correct |
| 2 |
Runtime error |
200 ms |
8976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
792 KB |
Output is correct |
| 2 |
Runtime error |
200 ms |
8976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
