#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vdd vector<pdd>
#define dte tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = 1e9 + 7;//998244353 ;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;
pii d[4] = { {1 , 0} , {0 , 1} , {-1 , 0} , {0 , -1} };
string dir = "NWSE";
map<char , int> mp;
int n , m , q;
vi adj[(int)7e5 + 10];
vi rev[(int)7e5 + 10];
vi g[(int)7e5 + 10];
bool vis[(int)7e5 + 10];
bool ok[(int)7e5 + 10];
int idx[(int)7e5 + 10];
stack<int> st;
vector<vi> scc;
string s;
int cur = 0;
vi v;
void dfs2(int pos){
if(vis[pos]) return ;
vis[pos] = true;
idx[pos] = cur;
v.pb(pos);
for(auto c : rev[pos]) dfs2(c);
}
void dfs(int pos){
if(vis[pos]) return;
vis[pos] = true;
for(auto c : adj[pos]) dfs(c);
st.push(pos);
}
int grid[808][808];
int nb[4];
int main(){
//ifstream fin ("testing.txt");
//ofstream fout ("output.txt");
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
for(int i = 0 ; i < 4 ; i++) mp[dir[i]] = i;
cin>>q>>n>>m;
cin>>s;
for(int i = 0 ; i < q ; i++){
int id = mp[s[i]];
for(int j = i + 1 ; j <= q ; j++){
if( j == q || s[j] != s[j- 1] ) {
nb[id] = max(nb[id] , j - i);
i = j - 1; break;
}
}
}
if(s[0] == s.back()){
int cnt = 1;
for(int i = 0 ; i < q - 1 ; i++){
if(s[i] != s[0]) break;
cnt++;
}
nb[mp[s[0]]] = max(nb[mp[s[0]]] , cnt);
}
//for(int i = 0 ; i < 4 ; i++) cout << nb[i] << endl;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++) cin>>grid[i][j];
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(grid[i][j] == 0) continue;
int a = i * m + j;
ok[a] = true;
for(int k = 0 ; k < 4 ; k++){
int x = i + d[k].ff , y = j + d[k].ss;
if(x < 0 || y < 0 || x == n || y == m) continue;
if(grid[x][y] == 0) continue;
int b = x * m + y;
//if(a == 2 && b == 3) cout << k << " " << grid[x][y] << "\n";
if(nb[k] >= grid[x][y]){
adj[a].pb(b); rev[b].pb(a);
}
}
}
}
n = (n - 1) * m + m;
/*for(int i = 0 ; i < n ; i++){
cout << i << " ";
for(auto c : adj[i]) cout << c << " "; cout << "\n";
}*/
for(int i = 0 ; i < n ; i++) if(!vis[i] && ok[i]) dfs(i);
memset(vis , 0 , sizeof vis);
while(!st.empty()){
int a = st.top(); st.pop();
if(vis[a]) continue;
dfs2(a);
scc.pb(v);
v.clear();
cur++;
}
/*cout << cur << "\n";
for(auto c : scc){
for(auto e : c) cout << e << " "; cout << "\n";
}*/
//memset(vis , 0 , sizeof vis);
for(int i = 0 ; i < n ; i++){
if(!ok[i]) continue;
for(auto c : adj[i]) if(idx[i] != idx[c]) g[idx[i]].pb(idx[c]);
}
int res = INF;
for(int i = 0 ; i < cur ; i++) if(g[i].empty()) res = min(res , (int)scc[i].size());
cout << res << " " << res << "\n";
return 0;
}
/*
Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD
Read the statement CAREFULLY !!
Make a GREADY APPROACH !!!! (start from highest / lowest)
Make your own TESTS !!
Be careful from CORNER CASES !
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
50428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
26 ms |
50364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
50428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
