This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ar array
//~ #define int long long
signed main(){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios::sync_with_stdio(0); cin.tie(0);
int k, n, m; cin>>k>>n>>m;
string s; cin>>s;
s += s;
vector<int> mx(1 << 4, 0), cur(1 << 4, 0);
for(int i=0;i<2*k;i++){
int c = 0;
if(s[i] == 'N') c = 0;
if(s[i] == 'E') c = 1;
if(s[i] == 'S') c = 2;
if(s[i] == 'W') c = 3;
for(int mask=0;mask<16;mask++){
if(mask >> c & 1) cur[mask]++;
else cur[mask] = 0;
mx[mask] = max(mx[mask], cur[mask]);
}
}
for(int i=0;i<16;i++){
if(mx[i] >= k) mx[i] = 1e9 + 7;
}
vector<vector<int>> a(n, vector<int>(m));
vector<int> ord;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
if(a[i][j]) ord.push_back(i * m + j);
}
}
shuffle(ord.begin(), ord.end(), rng);
int res = 1e9, cnt = 0;
vector<vector<int>> t(n, vector<int>(m)), used(n, vector<int>(m));
int tt = 0;
for(auto x : ord) t[x/m][x%m] = ++tt;
int ch[4][2] = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
auto check = [&](int i, int j){
if(!(0 <= i && i < n && 0 <= j && j < m) || a[i][j] == 0) return false;
int tot = 0;
for(int t=0;t<4;t++){
int x = i + ch[t][0], y = j + ch[t][1];
if(0 <= x && x < n && 0 <= y && y < m && used[x][y]) tot |= (1 << t);
}
return (mx[tot] >= a[i][j]);
};
for(auto x : ord){
int i = x/m, j = x%m;
vector<int> tot; tot.push_back(x);
queue<int> qq; qq.push(x);
used[i][j] = 1;
bool flag = 1;
while(!qq.empty() && flag){
int x = qq.front() / m, y = qq.front() % m; qq.pop();
for(int k=0;k<4;k++){
int r = x + ch[k][0], c = y + ch[k][1];
if(check(r, c) && !used[r][c]) {
used[r][c] = 1, qq.push(r * m + c);
tot.push_back(r * m + c);
if(t[r][c] < t[i][j]) { flag = 0; break; }
}
}
}
for(auto x : tot) used[x/m][x%m] = 0;
if(!flag) continue;
int sz = (int)tot.size();
if(sz < res) res = sz, cnt = 0;
cnt += (sz == res);
}
cout<<res<<"\n"<<cnt * res<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |