Submission #927551

#	Time	Username	Problem	Language	Result	Execution time	Memory
927551		Jawad_Akbar_JJ	Nautilus (BOI19_nautilus)	C++17	29 / 100	1059 ms	4956 KiB

nautilus

#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;
const int N = 100 + 10;
int n,m,k;
string s;
char a[N][N];
int seen[N][N][N];
int cur = 0;
int x[1000];
int y[1000];
queue<pair<pair<int,int>,int>> Q;

void deal(int i,int j,int ind,char d){
	i += x[d];
	j += y[d];
	if (i > n or j > m or i < 1 or j < 1)
		return;
	if (seen[i][j][ind+1] != cur)
		Q.push({{i,j},ind+1});
	seen[i][j][ind+1] = cur;
}

void bfs(int sr,int sc){
	cur++;
	Q.push({{sr,sc},0});
	seen[sr][sc][0] = cur;
	// cout<<sr<<" "<<sc<<endl;
	while (!Q.empty()){
		auto [a1,ind] = Q.front();
		Q.pop();
		auto [i,j] = a1;
		// cout<<i<<" "<<j<<" "<<ind<<endl;
		if (a[i][j] == '#')
			continue;
		if (ind == k){
			seen[0][i][j] = true;
			continue;
		}
				if (s[ind] != '?')
			deal(i,j,ind,s[ind]);
		else{
			deal(i,j,ind,'N');
			deal(i,j,ind,'E');
			deal(i,j,ind,'S');
			deal(i,j,ind,'W');
		}
	}
}

signed  main(){
	x['N'] = y['W'] = -1;
	x['S'] = y['E'] = 1;


	cin>>n>>m>>k;

	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			cin>>a[i][j];
	cin>>s;
	// cout<<"done"<<endl;

	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			bfs(i,j);
	int ans = 0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (ans += seen[0][i][j]);
	cout<<ans<<endl;
}

Compilation message (stderr)

nautilus.cpp: In function 'void deal(int, int, int, char)':
nautilus.cpp:21:9: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |  i += x[d];
      |         ^
nautilus.cpp:22:9: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |  j += y[d];
      |         ^

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