Submission #1187730

#TimeUsernameProblemLanguageResultExecution timeMemory
1187730KhizriNautilus (BOI19_nautilus)C++20
66 / 100
1093 ms5004 KiB
#pragma GCC optimize ("O3") #include <bits/stdc++.h> using namespace std; //------------------------------DEFINE------------------------------ //****************************************************************** #define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0) #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9+7) #define endl "\n" mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //****************************************************************** //----------------------------FUNCTION------------------------------ //****************************************************************** ll gcd(ll a,ll b){ if(a>b) swap(a,b); if(a==0) return a+b; return gcd(b%a,a); } ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } bool is_prime(ll n){ ll k=sqrt(n); if(n==2) return true; if(n<2||n%2==0||k*k==n) return false; for(int i=3;i<=k;i+=2){ if(n%i==0){ return false; } } return true; } //***************************************************************** //--------------------------MAIN-CODE------------------------------ const int mxn=500+5; int t=1, n, m, k, cnt = 0; char arr[mxn][mxn]; int res[mxn][mxn]; char s[mxn * 10]; set<int> st[mxn * 10]; int l[4] = {1, -1, 0, 0}; int r[4] = {0, 0, 1, -1}; bool ok = false; void rec(int i, int j, int idx){ if(idx == k){ res[i][j] = 1; return; } if(st[idx].count((i - 1) * m + j)){ return; } st[idx].insert((i - 1) * m + j); if(s[idx] == '?'){ for(int id = 0; id < 4; id++){ int a = i + l[id], b = j + r[id]; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.'){ rec(a, b, idx + 1); } } } else if(s[idx] == 'E'){ int a = i, b = j + 1; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.'){ rec(a, b, idx + 1); } } else if(s[idx] == 'S'){ int a = i + 1, b = j; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.'){ rec(a, b, idx + 1); } } else if(s[idx] == 'W'){ int a = i, b = j - 1; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.'){ rec(a, b, idx + 1); } } else if(s[idx] == 'N'){ int a = i - 1, b = j; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.'){ rec(a, b, idx + 1); } } } void solve(){ cin >> n >> m >> k; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> arr[i][j]; } } for(int i = 1; i <= k; i++){ cin >> s[i]; } queue<array<int, 3>> q; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(arr[i][j] == '.'){ res[i][j] = 1; q.push({i, j, 1}); } } } int i, j, idx; while(q.size()){ array<int, 3> qx = q.front(); q.pop(); i = qx[0], j = qx[1], idx = qx[2]; if(idx == k + 1){ continue; } if(s[idx] == '?'){ for(int id = 0; id < 4; id++){ int a = i + l[id], b = j + r[id]; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.' && idx + 1 > res[a][b]){ res[a][b] = idx + 1; q.push({a, b, idx + 1}); } } } else if(s[idx] == 'E'){ int a = i, b = j + 1; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.' && idx + 1 > res[a][b]){ res[a][b] = idx + 1; q.push({a, b, idx + 1}); } } else if(s[idx] == 'S'){ int a = i + 1, b = j; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.' && idx + 1 > res[a][b]){ res[a][b] = idx + 1; q.push({a, b, idx + 1}); } } else if(s[idx] == 'W'){ int a = i, b = j - 1; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.' && idx + 1 > res[a][b]){ res[a][b] = idx + 1; q.push({a, b, idx + 1}); } } else if(s[idx] == 'N'){ int a = i - 1, b = j; if(a >= 1 && b >= 1 && a <= n && b <= m && arr[a][b] == '.' && idx + 1 > res[a][b]){ res[a][b] = idx + 1; q.push({a, b, idx + 1}); } } } int ans = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(arr[i][j] == '.' && res[i][j] == k + 1){ ans++; } } } cout << ans << endl; } int main(){ IOS; //cin>>t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...