제출 #180282

#제출 시각아이디문제언어결과실행 시간메모리
180282sochoNautilus (BOI19_nautilus)C++14
66 / 100
1040 ms888 KiB
#include "bits/stdc++.h"
using namespace std;

int a, b, m;
vector<vector<bool> > grid;
string s;

bool valid(int x, int y) {
	// cout << "! " << x << ' ' << y << endl;
	if (x < 0 || y < 0) return false;
	if (x >= a || y >= b) return false;
	return grid[x][y];
}

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main() {
	
	cin >> a >> b >> m;
	for (int i=0; i<a; i++) {
		string s;
		cin >> s;
		vector<bool> tr(b);
		for (int j=0; j<b; j++) {
			tr[j] = (s[j] == '.');
		}
		grid.push_back(tr);
	}
	cin >> s;
	s = ' ' + s;
	
	bool reach[a][b][2];
	memset(reach, 0, sizeof reach);
	for (int i=0; i<a; i++) {
		for (int j=0; j<b; j++) {
			reach[i][j][0] = valid(i, j);
		}
	}
	
	for (int STEP=1; STEP<=m; STEP++) {
		// ith step
		char st = s[STEP];
		for (int i=0; i<a; i++) {
			for (int j=0; j<b; j++) {
				if (valid(i, j)) {
					if (st == 'W') {
						reach[i][j][STEP%2] = (valid(i, j+1) && reach[i][j+1][(STEP+1)%2]);
					}
					else if (st == 'E') {
						reach[i][j][STEP%2] = (valid(i, j-1) && reach[i][j-1][(STEP+1)%2]);
					}
					else if (st == 'N') {
						reach[i][j][STEP%2] = (valid(i+1, j) && reach[i+1][j][(STEP+1)%2]);
					}
					else if (st == 'S') {
						reach[i][j][STEP%2] = (valid(i-1, j) && reach[i-1][j][(STEP+1)%2]);
					}
					else {
						reach[i][j][STEP%2] = false;
						for (int k=0; k<4; k++) {
							reach[i][j][STEP%2] |= (valid(i+dx[k], j+dy[k]) && reach[i+dx[k]][j+dy[k]][(STEP+1)%2]);
						}
					}
				}
				else {
					reach[i][j][STEP%2] = false;
				}
			}
		}
	}
	
	int c = 0;
	for (int i=0; i<a; i++) {
		for (int j=0; j<b; j++) {
			if (reach[i][j][m%2]) c++;
		}
	}	
	cout << c << endl;
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...