Submission #1294860

#TimeUsernameProblemLanguageResultExecution timeMemory
1294860azik21Nautilus (BOI19_nautilus)C++20
66 / 100
1094 ms5188 KiB
#include<iostream>
// #include<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#define int long long
#define pb push_back
#define all(v) (v).begin() , (v).end()
using namespace std;
const int N = 600;
int dp[N][N][2];
vector<pair<int ,int >>g[5]{ {{-1 , 0}} , {{1 , 0 }} , {{0 , -1 }} , {{0 , 1 }} , {{-1 , 0} , {1 , 0} , {0 , -1 } , {0 , 1 }}};
signed main(){

    ios_base::sync_with_stdio(0) , cin.tie(0);
    int n ,m , sz;
    cin >> n >> m >> sz;
    char c[n+1][m+1];
    for(int i=1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            char x ;
            cin >> x ;
            if(x =='.'){
                dp[i][j][0] = 1 ;
            }
            c[i][j] = x;
        }
    } 
    string s ;
    cin >> s ;
    s = '+'+s;
    vector<int>num(30 , 0 );
    string h = "NSWE?";
    int w = 0 ;
    for(auto it:h){
        num[it-62] = w++;
        // cout << it << ' ' << num[it-62] << ' '<< it-62 << '\n';
        // for(auto ko:g[num[it-62]])cout <<ko.first << ' ' << ko.second << '\n';
        // cout << '\n';
    }
    int cnt =0 ;
    for(int time = 1 ; time <= sz ; time++){
        for(int i= 1; i<= n ; i++){
            for(int j =1 ; j <= m; j++){
                if(!dp[i][j][0])continue;
                int type = num[s[time]-62];
                for(auto [x , y ]:g[type]){
                    int nx = x + i   , ny = j + y ;
                    if(nx < 1 || nx > n || ny > m || ny < 1 || c[nx][ny]=='#')continue;
                    if(dp[i][j][0]){
                        dp[nx][ny][1] = 1 ;
                    }
                }
            }
        }
        for(int i= 1; i <= n ; i++){
            for(int j =1 ; j<= m; j++){
                if(time == sz){
                    if(dp[i][j][1]==1)cnt++;
                }
                dp[i][j][0] = dp[i][j][1];
                dp[i][j][1] =0 ;
            }
        }
    }
    cout<< cnt ;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...