Submission #860181

#	Time	Username	Problem	Language	Result	Execution time	Memory
860181		maks007	Nautilus (BOI19_nautilus)	C++14	0 / 100	8 ms	4184 KiB

nautilus

#include "bits/stdc++.h"

using namespace std;

int dp[100][100][100];
int it[] = {0, 0, 1, -1};
int jt[] = {1, -1, 0, 0};
map <char,pair <int,int>> mp;

signed main () {
	mp['W'] = {0, -1};
	mp['E'] = {0, 1};
	mp['N'] = {-1, 0};
	mp['S'] = {1, 0};
	int n, m, c;
	cin >> n >> m >> c;
	string a[n];
	for(int i = 0; i < n; i ++) {
		cin >> a[i];
	}
	string str;
	function <int(char,int,int)> f=[&](char ch, int i, int j) {
		i += mp[ch].first;
		j += mp[ch].second;
		if(i < 0 || j < 0 || i >= n || j >= m || a[i][j] == '#') return 0;
		return 1;
	};
	cin >> str;
	for(int i = str.size() - 1; i >= 0; i --) {
		for(int posi = 0; posi < n; posi ++) {
			for(int posj = 0; posj < m; posj ++) {
				if(a[posi][posj] == '#') {
					dp[i][posi][posj] = 0;
					continue;
				}
				if(i == str.size() - 1) {
					if(str[i] == '?') {
						dp[i][posi][posj] = f('E', posi, posj) + f('W', posi, posj) + f('S', posi, posj) + f('N', posi, posj);
					}else {
						dp[i][posi][posj] = f(str[i], posi, posj);
					}
				}else {
					if(str[i] == '?') {
						for(int to = 0; to < 4; to ++) {
							if(posi+it[to] < 0 || posi + it[to] >= n || posj + jt[to] < 0 || posj + jt[to] >= m || a[posi+it[to]][posj+jt[to]] == '#') continue;
							dp[i][posi][posj] += dp[i+1][posi+it[to]][posj+jt[to]];
						}
					}else {
						dp[i][posi][posj] = dp[i+1][posi+mp[str[i]].first][posj+mp[str[i]].second];
					}
				}
			}
		}
	}
	// for(int i = str.size() - 1; i >= 0; i --) {
	// 	for(int posi = 0; posi < n; posi ++) {
	// 		for(int posj = 0; posj < m; posj ++) {
	// 			cout << dp[i][posi][posj] << " ";
	// 		}
	// 		cout << "\n";
	// 	}
	// 	cout << "\n";
	// }
	int ans = 0;
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) ans += dp[0][i][j];
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(i == str.size() - 1) {
      |        ~~^~~~~~~~~~~~~~~~~

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