Submission #927528

#TimeUsernameProblemLanguageResultExecution timeMemory
927528Faisal_SaqibNautilus (BOI19_nautilus)C++17
66 / 100
1041 ms74320 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...