Submission #154944

#	Time	Username	Problem	Language	Result	Execution time	Memory
154944		GoldNextYear	Nautilus (BOI19_nautilus)	C++14	66 / 100	52 ms	11064 KiB

nautilus

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;
const ll inf=1e18*4;
const ld pai=acos(-1);
int n,m,k;
string path;
string s[109];
int dp[109][109][109];
int done[109][109];
int bt(int id,int x,int y){
        if(s[x][y]=='#')return 0;
        int &ret=dp[id][x][y];
        if(ret!=-1)return 0;
        if(id==k){
                if(done[x][y]==0){
                        done[x][y]=1;
                        return 1;
                }
                else return 0;
        }
        ret=0;
        if(path[id]=='N' && x-1>=0)ret+=bt(id+1,x-1,y);
        if(path[id]=='S' && x+1<n)ret+=bt(id+1,x+1,y);
        if(path[id]=='E' && y+1<m)ret+=bt(id+1,x,y+1);
        if(path[id]=='W' && y-1>=0)ret+=bt(id+1,x,y-1);
        if(path[id]=='?'){
                if(x-1>=0)ret+=bt(id+1,x-1,y);
                if(x+1<n)ret+=bt(id+1,x+1,y);
                if(y+1<m)ret+=bt(id+1,x,y+1);
                if(y-1>=0)ret+=bt(id+1,x,y-1);
        }
        return ret;
}
int main(){
        mem(dp,-1);
        cin>>n>>m>>k;
        for(int i=0;i<n;i++)cin>>s[i];
        cin>>path;
        int sum=0;
        for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                        if(s[i][j]!='#')sum+=bt(0,i,j);
                }
        }
        cout<<sum<<endl;
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34