Submission #414697

#	Time	Username	Problem	Language	Result	Execution time	Memory
414697		milleniumEeee	Nautilus (BOI19_nautilus)	C++11	66 / 100	1093 ms	2512 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];
bool possible[4];
 
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);
		for (int k = 0; k < 4; k++) {
			possible[k] = 0;
		}
		if (mp[step] == '?') {
			for (int k = 0; k < 4; k++) {
				possible[k] = 1;
			}
		} else {
			possible[pos[mp[step]]] = 1;
		}
		bool live = false;
		for (int y = 1; y <= r; y++) {
			for (int x = 1; x <= c; x++) {
				if (dp[prev][y][x] == used_id) {
					for (int cc = 0; cc < 4; cc++) {
						if (!possible[cc]) {
							continue;
						}
						int nY = y + toY[cc];
						int nX = x + toX[cc];
						if (in(nY, nX, r, c) && tp[nY][nX] == '.') {
							dp[cur][nY][nX] = used_id + 1;
							live = true;
						}
					}
				}
			}
		}
		if (!live) {
			used_id = 1e9;
			break;
		}
		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:62:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |    possible[pos[mp[step]]] = 1;
      |                         ^

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