제출 #968684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
968684		NintsiChkhaidze	Nautilus (BOI19_nautilus)	C++17	66 / 100	1066 ms	604 KiB

nautilus

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h*2),l,(l + r)/2
#define right (h*2+1),(l+r)/2 + 1,r
#define pii pair <int,int>
using namespace std;

const int N = 505;
char a[N][N];
vector <pii> neighbours = {{0,1}, {0,-1}, {1,0}, {-1,0}};
int n,m;
bitset <501> dpold[N],dpnew[N];

bool valid(int x,int y){
	return (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '.');
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int k;
	cin>>n>>m>>k;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
			if (a[i][j] == '.') dpold[i][j] = 1;
		}

	string s;
	cin>>s;

	map <char,pii> mp;
	mp['N'] = {-1,0};
	mp['S'] = {1,0};
	mp['E'] = {0,+1};
	mp['W'] = {0,-1};

	for (int i = 0; i < k; i++){

		for (int x = 1; x <= n; x++){
			for (int y = 1; y <= m; y++){
				if (!dpold[x][y]) continue;

				if (s[i] != '?'){
					int dx = mp[s[i]].f,dy = mp[s[i]].s;
					int X = x + dx,Y = y + dy;
					if (valid(X,Y)) dpnew[X][Y] = 1;
					continue;
				}

				for (auto [dx,dy]: neighbours){
					int X = x + dx,Y = y + dy;
					if (valid(X,Y)) dpnew[X][Y] = 1;
				}

			}
		}
		for (int x=1;x<=n; x++)	
			dpold[x] = dpnew[x],dpnew[x] = 0;
	}

	int ans=0;
	for (int i = 1; i <= n; i++)
		ans += dpold[i].count();
	cout<<ans;
}

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