Submission #927518

#TimeUsernameProblemLanguageResultExecution timeMemory
927518Muhammad_AneeqNautilus (BOI19_nautilus)C++17
66 / 100
1068 ms174684 KiB
/* بسم الله الرحمن الرحيم Author: (:Muhammad Aneeq:) */ #include <iostream> #include <vector> #include <queue> using namespace std; int r,c,m; int const R=500+10; int const M=5000+10; vector<vector<char>>a(R,vector<char>(R)); string s; int ans=0; vector<vector<vector<bool>>>vis(R,vector<vector<bool>>(R,vector<bool>(M))); queue<pair<int,pair<int,int>>>Q; inline bool check(int i,int j,int ind) { if (i<0||i>=r||j<0||j>=c||a[i][j]=='#'||vis[i][j][ind]) return 0; Q.push({ind,{i,j}}); vis[i][j][ind]=1; return 1; } inline void bfs(int i,int j) { check(i,j,0); while (Q.size()) { auto z=Q.front(); Q.pop(); int ind=z.first,i=z.second.first,j=z.second.second; if (ind==m) { ans++; return; } if (s[ind]=='?') { check(i+1,j,ind+1); check(i,j+1,ind+1); check(i-1,j,ind+1); check(i,j-1,ind+1); } if (s[ind]=='N') check(i-1,j,ind+1); if (s[ind]=='S') check(i+1,j,ind+1); if (s[ind]=='E') check(i,j+1,ind+1); if (s[ind]=='W') check(i,j-1,ind+1); } } inline void solve() { cin>>r>>c>>m; for (int i=0;i<r;i++) for (int j=0;j<c;j++) cin>>a[i][j]; cin>>s; for (int i=0;i<r;i++) for (int j=0;j<c;j++) bfs(i,j); cout<<ans<<endl; } int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...