Submission #927528

#	Time	Username	Problem	Language	Result	Execution time	Memory
927528		Faisal_Saqib	Nautilus (BOI19_nautilus)	C++17	66 / 100	1041 ms	74320 KiB

nautilus

#include <iostream>
#include <bitset>
using namespace std;
char g[250000];
int n,m,M;
char s[5001];
bitset<250000> pos[5002];
bitset<250000> fx[5002];
bool dfs(int x,int y,int ind)
{
  if(x<0 or y<0 or x>=n or y>=m or g[(x*m)+y]=='#')
    return 0;
  if(fx[ind][(x*m)+y])
    return pos[ind][(x*m)+y];
  fx[ind][(x*m)+y]=1;
  if(ind==M)
    return pos[ind][(x*m)+y]=1;
  if(s[ind]=='?')
    pos[ind][(x*m)+y]=(dfs(x-1,y,ind+1)|dfs(x+1,y,ind+1)|dfs(x,y-1,ind+1)|dfs(x,y+1,ind+1));
  else if(s[ind]=='N')
    pos[ind][(x*m)+y]=dfs(x-1,y,ind+1);   
  else if(s[ind]=='S')
    pos[ind][(x*m)+y]=dfs(x+1,y,ind+1);
  else if(s[ind]=='W')
    pos[ind][(x*m)+y]=dfs(x,y-1,ind+1);   
  else if(s[ind]=='E')
    pos[ind][(x*m)+y]=dfs(x,y+1,ind+1);
  return pos[ind][(x*m)+y];
}
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
  cin>>n>>m>>M;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      cin>>g[(i*m)+j];
  for(int j=0;j<M;j++)
    cin>>s[j];
  int cnt=0;
  for(int x=0;x<n;x++)
    for(int y=0;y<m;y++)
      dfs(x,y,0);
  for(int x=0;x<n;x++)
    for(int y=0;y<m;y++)
      cnt+=pos[M][(x*m)+y];
  cout<<cnt<<'\n';
}

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