Submission #1111150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111150		Ghulam_Junaid	Nautilus (BOI19_nautilus)	C++17	66 / 100	163 ms	262144 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
 
const int N = 505;
const int M = 5005;
 
int n, m, q;
string s;
char mat[N][N];
bool dp[N][N][M];
 
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
//           N  E  S   W
map<char, int> mp;
 
bool valid(int x, int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m && mat[x][y] != '#');
}
 
int main(){
    mp['N'] = 0, mp['E'] = 1, mp['S'] = 2, mp['W'] = 3;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> mat[i][j];
    cin >> s;
    s = '_' + s;
 
    for (int k = 0; k <= q; k ++){
        for (int x = 1; x <= n; x ++){
            for (int y = 1; y <= m; y ++){
                if (!valid(x, y)) continue;
                if (k == 0){
                    dp[x][y][k] = 1;
                    continue;
                }
 
                if (s[k] == '?'){
                    for (int d = 0; d < 4; d ++){
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        dp[x][y][k] |= dp[nx][ny][k - 1];
                    }
                }
                else{
                    int d = (mp[s[k]] + 2) % 4;
 
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    dp[x][y][k] = dp[nx][ny][k - 1];
                }
            }
        }
    }
 
    int ans = 0;
    for (int x = 1; x <= n; x ++)
        for (int y = 1; y <= m; y ++)
            ans += dp[x][y][q];
    cout << ans << endl;
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34