제출 #1016804

#제출 시각아이디문제언어결과실행 시간메모리
1016804ByeWorldNautilus (BOI19_nautilus)C++14
29 / 100
6 ms1628 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") #define ll long long #define int long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<pii, int> ipii; const int MAXN = 110; const int MAXA = 110; const int INF = 1e18+10; const int LOG = 19; const int MOD = 1e9+7; const int SQRT = 450; const vector<int> NOL = {}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const vector<int> dx = {1, -1, 0, 0}; const vector<int> dy = {0, 0, 1, -1}; void chmx(int &a, int b){ a = max(a, b); } int n, m, k; char c[MAXN][MAXN]; bool dp[MAXN][MAXN][MAXA]; string s; bool valid(int x, int y){ if(x<1||x>n||y<1||y>m||c[x][y]=='#') return 0; return 1; } signed main(){ // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m >> k; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> c[i][j]; cin >> s; s = '.'+s; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) dp[i][j][k+1] = valid(i, j); for(int id=k; id>=1; id--){ for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(!valid(i, j)) continue; if(s[id] == '?'){ for(int pp=0; pp<4; pp++){ int nx = i+dx[pp], ny = j+dy[pp]; if(!valid(nx, ny)) continue; dp[i][j][id] |= dp[nx][ny][id+1]; } } else { int nx = -1, ny = -1; if(s[id]=='W'){ nx = i, ny = j-1; if(!valid(nx, ny)) continue; dp[i][j][id] |= dp[nx][ny][id+1]; } else if(s[id]=='E'){ nx = i, ny = j+1; if(!valid(nx, ny)) continue; dp[i][j][id] |= dp[nx][ny][id+1]; } else if(s[id]=='N'){ nx = i-1, ny = j; if(!valid(nx, ny)) continue; dp[i][j][id] |= dp[nx][ny][id+1]; } else if(s[id]=='S'){ nx = i+1, ny = j; if(!valid(nx, ny)) continue; dp[i][j][id] |= dp[nx][ny][id+1]; } } } } // cout << id << " kk\n"; // for(int i=1; i<=n; i++) // for(int j=1; j<=m; j++) cout << dp[i][j][id] << " \n"[j==m]; } int ANS = 0; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ANS += dp[i][j][1]; // for(int i=1; i<=n; i++) // for(int j=1; j<=m; j++) cout << dp[i][j][1] << " \n"[j==m]; cout << ANS << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...