Submission #860277

#	Time	Username	Problem	Language	Result	Execution time	Memory
860277		iskhakkutbilim	Nautilus (BOI19_nautilus)	C++17	66 / 100	1089 ms	52912 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];
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];
		}
	}
	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;
	vector< pair<int, int> > cells;
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m; j++){
			if(a[i][j] != '#') cells.push_back({i, j});
		}
	}
	for(char ch : s){
		vector<pair<int, int> > new_cells;
		for(auto [i, j] : cells){
			for(auto [x, y] : mp[ch]){
				if(in(i + x, j + y)){
					new_cells.push_back({i + x, j + y});
				}
			}
		}
		swap(cells, new_cells);
		if(new_cells.empty()){
			break;
		}
		
		sort(all(cells));
		cells.erase(unique(all(cells)), cells.end());
		
	}
	cout << cells.size();
	return 0;
}

Compilation message (stderr)

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

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