제출 #1214372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214372		g4yuhg	Nautilus (BOI19_nautilus)	C++20	100 / 100	151 ms	784 KiB

nautilus

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 100010
using namespace std;

bool ghuy4g;

const ll hx[] = {-1, 0, 1, 0};
const ll hy[] = {0, 1, 0, -1};
// N E S W
// ^ > v <
ll r, c, m;
char a[505][505];
bitset<505> dp[2][505], goc[505];
void move(ll huong) {
	if (huong == 0) {
		for (int i = 1; i <= r; i ++) {
			dp[1][i] = dp[0][i + 1];
			dp[1][i] = dp[1][i] & goc[i];
		}
		for (int i = 1; i <= r; i ++) {
			dp[0][i] = dp[1][i];
		}
	}
	else if (huong == 2) {
		for (int i = 1; i <= r; i ++) {
			dp[1][i] = dp[0][i - 1];
			dp[1][i] = dp[1][i] & goc[i];
		}
		for (int i = 1; i <= r; i ++) {
			dp[0][i] = dp[1][i];
		}
	}
	else if (huong == 1) {
		for (int i = 1; i <= r; i ++) {
			//dp[1][i] = (dp[0][i] >> 1);
			dp[1][i] = (dp[0][i] << 1);
			dp[1][i] = dp[1][i] & goc[i];
		}
		for (int i = 1; i <= r; i ++) {
			dp[0][i] = dp[1][i];
		}
	}
	else if (huong == 3){
		for (int i = 1; i <= r; i ++) {
			//dp[1][i] = (dp[0][i] << 1);
			dp[1][i] = (dp[0][i] >> 1);
			dp[1][i] = dp[1][i] & goc[i];
		}
		for (int i = 1; i <= r; i ++) {
			dp[0][i] = dp[1][i];
		}
	}
	else {
		for (int i = 1; i <= r; i ++) {
			dp[1][i] = (dp[0][i - 1] | dp[0][i + 1] | (dp[0][i] >> 1) | (dp[0][i] << 1));
			dp[1][i] = dp[1][i] & goc[i];
		}
		for (int i = 1; i <= r; i ++) {
			dp[0][i] = dp[1][i];
		}
	}
}

bool klinh;

signed main(void) {
    faster;	
    cin >> r >> c >> m;
    for (int i = 1; i <= r; i ++) {
    	for (int j = 1; j <= c; j ++) {
    		cin >> a[i][j];
    		if (a[i][j] == '.') {
    			dp[0][i].set(j);
    			goc[i].set(j);
    			//cout << i << " " << j << endl;
    		}
    	}
    }
    map<char, ll> mp;
    mp['N'] = 0, mp['E'] = 1, mp['S'] = 2, mp['W'] = 3;
    for (int i = 1; i <= m; i ++) {
    	char C; cin >> C;
    	if (C != '?') {
    		ll id = mp[C];
    		move(id);
    	}
    	else {
    		move(-1);
    	}
    	/*for (int id = 1; id <= r; id ++) {
    		for (int jd = 1; jd <= c; jd ++) {
    			cout << dp[0][id][jd] << " ";
    		}
    		cout << endl;
    	}*/
    }
    ll ans = 0;
    for (int i = 1; i <= r; i ++) {
    	for (int j = 1; j <= c; j ++) {
    		ans = ans + (dp[0][i][j] == 1);
    	}
    }
    cout << ans;
    cerr << fabs ((&ghuy4g - &klinh) / 1048576.0);
    return 0;
}

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