Submission #860467

#	Time	Username	Problem	Language	Result	Execution time	Memory
860467		iskhakkutbilim	Nautilus (BOI19_nautilus)	C++17	66 / 100	1085 ms	4696 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
 
 
int n, m, q;
char a[501][501];
int dp[501][501];
string s;
int in(int i, int j){
	return (i >= 1 && j >= 1 && i <= n && j <= m and a[i][j] == '.');
}
 
map<char, vector<pair<int, int> > >mp;
 
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m; j++){
			cin >> a[i][j];
			if(a[i][j] != '#') dp[i][j] = 1;
		}
	}
	mp['N'].push_back({-1, 0});
	mp['S'].push_back({1, 0});
	mp['E'].push_back({0, 1});
	mp['W'].push_back({0, -1});
 
	mp['?'].push_back({-1, 0});
	mp['?'].push_back({1, 0});
	mp['?'].push_back({0, 1});
	mp['?'].push_back({0, -1});
	cin >> s;
	for(char ch : s){
		int new_dp[501][501];
		memset(new_dp, 0, sizeof(new_dp));
		for(int i = 1;i <= n; i++){
			for(int j = 1;j <= m; j++){
				if(dp[i][j]){
					for(auto [x, y] : mp[ch]){
						if(in(i + x, j + y)){
							new_dp[i + x][j + y]|= dp[i][j];
						}
					}
				}
			}
		}
		swap(dp, new_dp);
	}
	int ans = 0;
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m; j++){
			if(dp[i][j]) ans++;
//			ans+= dp[i][j];
		}
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

nautilus.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main(){
      | ^~~~

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