Submission #1153262

#TimeUsernameProblemLanguageResultExecution timeMemory
1153262brover29Remittance (JOI19_remittance)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=805;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,m,a[N][N],used[N][N],cnt[N],ans,b[N][N];
map<ll,ll>mp;
ll dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
void dfs(ll x,ll y){
    ans++;
    used[x][y]=1;
    //cout<<x<<' '<<y<<'\n';
    for(ll i=0;i<4;i++){
        ll nx=x+dx[i];
        ll ny=y+dy[i];
        if(nx<1||nx>n||ny<1||ny>m||used[nx][ny]||!a[nx][ny])continue;
        b[nx][ny]+=cnt[i];
        if(b[nx][ny]>=a[nx][ny])dfs(nx,ny);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll x;
    cin>>x>>n>>m;
    string s;
    cin>>s;
    for(char i:s){
        if(i=='S')cnt[3]++;
        if(i=='N')cnt[1]++;
        if(i=='W')cnt[0]++;
        if(i=='E')cnt[2]++;
    }for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }ll mx=1e18;
    ll cnt=0;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(!a[i][j])continue;
            for(ll i=1;i<=n;i++){
                for(ll j=1;j<=m;j++){
                    used[i][j]=0;
                    b[i][j]=0;
                }
            }ans=0;
            dfs(i,j);
            //cout<<i<<' '<<j<<' '<<ans<<'\n';
            if(ans<mx){
                mx=ans;
                cnt=0;
            }
            if(ans==mx){
                cnt++;
            }
        }
    }

    cout<<mx<<'\n'<<cnt;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...