Submission #171053

#	Time	Username	Problem	Language	Result	Execution time	Memory
171053		dndhk	Nautilus (BOI19_nautilus)	C++14	66 / 100	1069 ms	5988 KiB

nautilus

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 500;

int N, M, Q;
string arr[MAX_N+1];
bool dp[MAX_N+1][MAX_N+1];
string str;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
char c[4] = {'E', 'W', 'S', 'N'};

bool chk(int x, int y){
	if(x<0 || x>=N || y<0 || y>=M)	return false;
	return (arr[x][y]=='.');
}
vector<pii> vt[2];
void add(int x, int y){
	if(!dp[x][y]){
		dp[x][y] = true;
		vt[1].pb({x, y});
	}
}

int main(){
	scanf("%d%d%d", &N, &M, &Q);	
	for(int i=0; i<N; i++){
		cin>>arr[i];
		for(int j=0; j<M; j++){
			if(arr[i][j]=='.'){
				vt[0].pb({i, j});
			}
			//dp[0][i][j] = (arr[i][j]=='.');
			//cout<<dp[0][i][j];
		}//cout<<endl;
	}
	cin>>str;
	for(int k=0; k<Q; k++){
		if(str[k]=='?'){
			for(pii p : vt[0]){
				int i = p.first, j = p.second;
				for(int k=0; k<4; k++){
					if(chk(i+dx[k], j+dy[k])){
						add(i+dx[k], j+dy[k]);
					}
				}
			}
		}else{
			int t;
			for(t=0; t<4; t++){
				if(str[k]==c[t])	break;
			}
			//cout<<t<<endl;
			for(pii p : vt[0]){
				int i = p.first, j = p.second;
				if(chk(i+dx[t], j+dy[t])){
					add(i+dx[t], j+dy[t]);
				}	
			}	
		}
		while(!vt[0].empty())	vt[0].pop_back();
		while(!vt[1].empty()){
			vt[0].pb(vt[1].back());
			dp[vt[1].back().first][vt[1].back().second] = false;
			vt[1].pop_back();
		}
	}
	cout<<vt[0].size();
	return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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