Submission #180279

#	Time	Username	Problem	Language	Result	Execution time	Memory
180279		socho	Nautilus (BOI19_nautilus)	C++14	66 / 100	46 ms	6220 KiB

nautilus

#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};

const int MXN = 105, MXM = 105;
bool done[MXN][MXN][MXM];
bool dp[MXN][MXN][MXM];

bool works(int x, int y, int at) {
	if (!valid(x, y)) return false;
	if (at == m) return true;
	if (done[x][y][at]) return dp[x][y][at];
	done[x][y][at] = true;
	if (s[at] == '?') {
		for (int i=0; i<4; i++) {
			if (works(x + dx[i], y + dy[i], at+1)) return dp[x][y][at] = true;
		}
		return dp[x][y][at] = false;
	}
	if (s[at] == 'N') {
		return dp[x][y][at] = works(x-1, y, at+1);
	}
	if (s[at] == 'S') {
		return dp[x][y][at] = works(x+1, y, at+1);
	}
	if (s[at] == 'E') {
		return dp[x][y][at] = works(x, y+1, at+1);
	}
	if (s[at] == 'W') {
		return dp[x][y][at] = works(x, y-1, at+1);
	}
	return dp[x][y][at] = false;
}

char op(char a) {
	if (a == 'N') return 'S';
	if (a == 'S') return 'N';
	if (a == 'E') return 'W';
	if (a == 'W') return 'E';
	return a;
}

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;
	string t = "";
	for (int i=0; i<m; i++) {
		t += op(s[i]);
	}
	s = t;
	reverse(s.begin(), s.end());
	
	int can = 0;
	for (int i=0; i<a; i++) {
		for (int j=0; j<b; j++) {
			if (works(i, j, 0)) {
				can++;
				// cout << "ok: " << i << ' ' << j << endl;
			}
			// cout << "----" << endl;
		}
	}
	cout << can << endl;
	
	
}

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