#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()<100000){
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,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];
rep(i,0,r){
rep(j,0,c){
cin>>u[i][j];
}
}
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:90: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]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
760 KB |
Output is correct |
2 |
Execution timed out |
2056 ms |
5948 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
632 KB |
Output is correct |
2 |
Correct |
10 ms |
760 KB |
Output is correct |
3 |
Correct |
24 ms |
636 KB |
Output is correct |
4 |
Correct |
11 ms |
760 KB |
Output is correct |
5 |
Correct |
23 ms |
632 KB |
Output is correct |
6 |
Correct |
185 ms |
1144 KB |
Output is correct |
7 |
Correct |
6 ms |
632 KB |
Output is correct |
8 |
Correct |
23 ms |
888 KB |
Output is correct |
9 |
Correct |
75 ms |
760 KB |
Output is correct |
10 |
Correct |
11 ms |
760 KB |
Output is correct |
11 |
Correct |
23 ms |
856 KB |
Output is correct |
12 |
Correct |
192 ms |
988 KB |
Output is correct |
13 |
Correct |
111 ms |
1164 KB |
Output is correct |
14 |
Correct |
103 ms |
1144 KB |
Output is correct |
15 |
Correct |
111 ms |
1256 KB |
Output is correct |
16 |
Correct |
97 ms |
888 KB |
Output is correct |
17 |
Correct |
34 ms |
888 KB |
Output is correct |
18 |
Correct |
58 ms |
888 KB |
Output is correct |
19 |
Correct |
36 ms |
1016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
760 KB |
Output is correct |
2 |
Execution timed out |
2056 ms |
5948 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |