Submission #123206

#TimeUsernameProblemLanguageResultExecution timeMemory
123206miguelNautilus (BOI19_nautilus)C++14
66 / 100
17 ms1400 KiB
#include<bits/stdc++.h> using namespace std; #define rc(x) return cout<<x<<endl,0 #define pb push_back #define dbg(x) cout << #x << '=' << x << '\n'; #define ll long long #define sz size() #define x first #define y second #define pi pair <int, int> #define pii pair <pi, int> #define vi vector <int> const ll mod = 1000000007; //#define int ll int n, m, ss, ans; set <pi> mp; bool t[101][101]; bool dp[102][101][101]; string s; bool valid(int x, int y){ if(x>0 && x<=n && y>0 && y<=m && t[x][y]) return 1; else return 0; } void dfs(int x, int y, int cur){ if(cur==ss){ if(valid(x, y)) mp.insert({x, y}); } else{ char c=s[cur]; if(c=='?'){ if(valid(x+1, y)) dfs(x+1, y, cur+1); if(valid(x, y+1)) dfs(x, y+1, cur+1); if(valid(x-1, y)) dfs(x-1, y, cur+1); if(valid(x, y-1)) dfs(x, y-1, cur+1); } else if(c=='S' && valid(x+1, y)) dfs(x+1, y, cur+1); else if(c=='E' && valid(x, y+1)) dfs(x, y+1, cur+1); else if(c=='N' && valid(x-1, y)) dfs(x-1, y, cur+1); else if(c=='W' && valid(x, y-1)) dfs(x, y-1, cur+1); } } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cin>>n>>m>>ss; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ char c; cin>>c; if(c=='#') t[i][j]=0; else t[i][j]=1; } } cin>>s; for(int cur=0; cur<ss; cur++){ for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(valid(i, j) && (cur==0 || dp[cur][i][j])){ int x=i, y=j; char c=s[cur]; //cout<<c; if(c=='?'){ if(valid(x+1, y)) dp[cur+1][x+1][y]=1, x++; x=i; y=j; if(valid(x, y+1)) dp[cur+1][x][y+1]=1, y++; x=i; y=j; if(valid(x-1, y)) dp[cur+1][x-1][y]=1, x--; x=i; y=j; if(valid(x, y-1)) dp[cur+1][x][y-1]=1, y--; } //else cout<<"x"; else if(c=='S'){ if(valid(x+1, y)) dp[cur+1][x+1][y]=1, x++; }//else cout<<(c=='W'); else if(c=='E'){ if(valid(x, y+1)) dp[cur+1][x][y+1]=1, y++; } else if(c=='N'){ if(valid(x-1, y)) dp[cur+1][x-1][y]=1, x--; } else if(c=='W'){ if(valid(x, y-1)) dp[cur+1][x][y-1]=1, y--; } } } } } //cout<<endl; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ //cout<<dp[1][i][j]; if(dp[ss][i][j]) ans++; } //cout<<endl; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...