Submission #945241

#	Time	Username	Problem	Language	Result	Execution time	Memory
945241		LucaIlie	Nautilus (BOI19_nautilus)	C++17	66 / 100	1060 ms	253212 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500;
const int MAX_K = 5000;
char mat[MAX_N + 2][MAX_N + 2];
set <pair <int, int>> dp[MAX_K + 1];
int dl[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };
int dir[256];

int main() {
    int n, m, k;

    dir['N'] = 0;
    dir['W'] = 1;
    dir['S'] = 2;
    dir['E'] = 3;

    cin >> n >> m >> k;
    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ )
            cin >> mat[l][c];
    }
    for ( int l = 0; l <= n + 1; l++ )
        mat[l][0] = mat[l][m + 1] = '#';
    for ( int c = 0; c <= m + 1; c++ )
        mat[0][c] = mat[n + 1][c] = '#';

    string moves;
    cin >> moves;
    moves = " " + moves;

    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ ) {
            if ( mat[l][c] == '.' )
                dp[0].insert( { l, c } );
        }
    }
    for ( int i = 1; i <= k; i++ ) {
        for ( pair <int, int> p: dp[i - 1] ) {
            if ( moves[i] == '?' ) {
                for ( int d = 0; d < 4; d++ ) {
                    int l = p.first + dl[d], c = p.second + dc[d];
                    if ( mat[l][c] == '.' )
                        dp[i].insert( { l, c } );
                }
            } else {
                int d = dir[moves[i]];
                int l = p.first + dl[d], c = p.second + dc[d];
                if ( mat[l][c] == '.' )
                    dp[i].insert( { l, c } );
            }
        }
    }


    cout << dp[k].size();

    return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:50:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |                 int d = dir[moves[i]];
      |                                     ^

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