Submission #927519

#TimeUsernameProblemLanguageResultExecution timeMemory
927519Faisal_SaqibNautilus (BOI19_nautilus)C++17
66 / 100
1101 ms136864 KiB
#include <iostream>
#include <bitset>
#include <map>
using namespace std;
char g[501][501];
int n,m,M;
string s;
map<char,pair<int,int>> dir;
bitset<5001> pos[501][501];
bitset<5001> fx[501][501];
bool dfs(int x,int y,int ind)
{
  if(x<0 or y<0 or x>=n or y>=m or g[x][y]=='#')
    return 0;
  if(fx[x][y][ind])
    return pos[x][y][ind];
  if(ind==M)
  {
    pos[x][y][ind]=1;
    fx[x][y][ind]=1;
    return 1;   
  }
  if(s[ind]=='?')
  {
    fx[x][y][ind]=1;
    for(auto lp:dir)
      if(dfs(x+lp.second.first,y+lp.second.second,ind+1))
        pos[x][y][ind]=1;
  }
  else
  {
    fx[x][y][ind]=1;
    pos[x][y][ind]=dfs(x+dir[s[ind]].first,y+dir[s[ind]].second,ind+1);   
  }
  return pos[x][y][ind];
}
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
  dir['N']={-1,0};
  dir['S']={1,0};
  dir['E']={0,1};
  dir['W']={0,-1};
  cin>>n>>m>>M;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      cin>>g[i][j];
  cin>>s;
  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[x][y][M];
  cout<<cnt<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...