Submission #496412

#TimeUsernameProblemLanguageResultExecution timeMemory
496412IerusNautilus (BOI19_nautilus)C++17
66 / 100
693 ms262148 KiB
#include<bits/stdc++.h> /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; */ using namespace std; #pragma GCC optimize ("unroll-loops,Ofast,O3") #pragma GCC target("avx,avx2,fma") #define F first #define int short #define S second #define sz(x) (int)x.size() #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ; #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) //#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> typedef long long ll; const long long inf = 1e18+777; const int N = 5555; const bool I = 1; const vector<pair<int,int>> dxy = {{1,0},{-1,0},{0,1},{0,-1}}; int n, m, k, q[5555]; char a[555][555]; bool vis[555][555]; int32_t res = 0; bool used[555][555][5555]; bool In(int x, int y){ return (x <= n && x >= 1 && y <= m && y >= 1); } void bfs(int x, int y, int d = 1){ deque<tuple<int,int,int>> dq; dq.pb({x, y, d}); while(!dq.empty()){ tie(x, y, d) = dq.front(); dq.pop_front(); if(d == k + 1){ if(!vis[x][y]){ vis[x][y] = true; ++res; } continue; } if(q[d] == -1){ for(auto [f, s] : dxy){ int x1 = x + f, y1 = y + s; if(In(x1, y1) && a[x1][y1] != '#' && !used[x1][y1][d+1]){ dq.pb({x1, y1, d+1}); used[x1][y1][d+1] = true; } } }else{ int x1 = x + dxy[q[d]].F, y1 = y + dxy[q[d]].S; if(In(x1, y1) && a[x1][y1] != '#' && !used[x1][y1][d+1]){ dq.pb({x1, y1, d+1}); used[x1][y1][d+1] = true; } } } } signed main(){NFS; cin >> n >> m >> k; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j){ cin >> a[i][j]; } } for(int i = 1; i <= k; ++i){ char r; cin >> r; if(r == '?') q[i] = -1; if(r == 'N') q[i] = 1; if(r == 'S') q[i] = 0; if(r == 'E') q[i] = 2; if(r == 'W') q[i] = 3; } for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j){ if(a[i][j] == '.'){ bfs(i, j, 1); } } cout << res; };
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...