Submission #414686

#	Time	Username	Problem	Language	Result	Execution time	Memory
414686		milleniumEeee	Nautilus (BOI19_nautilus)	C++11	66 / 100	1084 ms	2508 KiB

nautilus

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define prev prevw313131313
#define next next131313131
#define pb push_back
using namespace std;

const int MAXN = 505;

char tp[MAXN][MAXN];
int dp[2][MAXN][MAXN];
int used_id = 1;

int toY[] = {-1, 0, 1, 0};
int toX[] = {0, 1, 0, -1};

bool in(int y, int x, int r, int c) {
	return 1 <= y && y <= r && 1 <= x && x <= c;
}

int pos[1000];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int r, c, m;
	cin >> r >> c >> m;
	pos['N'] = 0;
	pos['E'] = 1;
	pos['S'] = 2;
	pos['W'] = 3;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> tp[i][j];
		}
	}
	string mp;
	cin >> mp;
	mp = ' ' + mp;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (tp[i][j] == '.') {
				dp[0][i][j] = used_id;
			}
		}
	}
	// 0 moves
	for (int step = 1; step <= m; step++) {
		int prev = ((step - 1) & 1);
		int cur = (step & 1);
		vector <int> possible;
		if (mp[step] == '?') {
			for (int k = 0; k < 4; k++) {
				possible.pb(k);
			}
		} else {
			possible.pb(pos[mp[step]]);
		}
		for (int y = 1; y <= r; y++) {
			for (int x = 1; x <= c; x++) {
				if (dp[prev][y][x] == used_id) {
					for (int el : possible) {
						int nY = y + toY[el];
						int nX = x + toX[el];
						if (in(nY, nX, r, c) && tp[nY][nX] == '.') {
							dp[cur][nY][nX] = used_id + 1;
						}
					}
				}
			}
		}
		used_id++;
	}
	int ans = 0;
	for (int y = 1; y <= r; y++) {
		for (int x = 1; x <= c; x++) {
			ans += (dp[(m & 1)][y][x] == used_id);
		}
	}
	cout << ans << endl;
}

/*
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
*/

Compilation message (stderr)

nautilus.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
nautilus.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
nautilus.cpp: In function 'int main()':
nautilus.cpp:59:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |    possible.pb(pos[mp[step]]);
      |                            ^

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