Submission #927570

#	Time	Username	Problem	Language	Result	Execution time	Memory
927570		Muhammad_Aneeq	Nautilus (BOI19_nautilus)	C++17	66 / 100	1073 ms	72216 KiB

nautilus

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
 
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
int r,c,m;
int const R=500+10;
int const M=5000+10;
char a[R][R]={};
string s;
int ans=0;
bitset<M>vis[R][R]={};
queue<pair<int,pair<int,int>>>Q;
inline bool check(int i,int j,int ind)
{
  if (i<0||i>=r||j<0||j>=c||a[i][j]=='#'||vis[i][j][ind])
    return 0;
  Q.push({ind,{i,j}});
  vis[i][j][ind]=1;
  return 1;
}
inline void bfs(int i,int j)
{
  check(i,j,0);
  while (Q.size())
  {
    auto z=Q.front();
    Q.pop();
    int ind=z.first,i=z.second.first,j=z.second.second;
    if (ind==m)
    {
      ans++;
      return;
    }
      if (s[ind]=='?')
    {
      check(i+1,j,ind+1);
      check(i,j+1,ind+1);
      check(i-1,j,ind+1);
      check(i,j-1,ind+1);
    }
    if (s[ind]=='N')
      check(i-1,j,ind+1);
    if (s[ind]=='S')
      check(i+1,j,ind+1);
    if (s[ind]=='E')
      check(i,j+1,ind+1);
    if (s[ind]=='W')
      check(i,j-1,ind+1);
  }
}
inline void solve()
{
  cin>>r>>c>>m;
  for (int i=0;i<r;i++)
    for (int j=0;j<c;j++)
      cin>>a[i][j];
  cin>>s;
  for (int i=0;i<r;i++)
    for (int j=0;j<c;j++)
      bfs(i,j);
  cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

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