Submission #927880

#	Time	Username	Problem	Language	Result	Execution time	Memory
927880		KaleemRazaSyed	Nautilus (BOI19_nautilus)	C++17	100 / 100	142 ms	1368 KiB

nautilus

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 505;
bitset<N> st[N], newst[N], null[N], W[N], E[N], No[N], S[N];
string s[N];
int r, c, m;
 
inline void update()
{
  for(int i = 0; i < r; i ++)
    st[i] = newst[i], newst[i] = null[i];
}
 
inline void move_West()
{
  for(int i = 0; i < r; i ++)
    newst[i] |= (st[i] >> 1) & W[i];
}
 
inline void move_East()
{
  for(int i = 0; i < r; i ++)
    newst[i] |= (st[i] << 1) & E[i];
}
 
inline void move_North()
{
  for(int i = 0; i + 1 < r; i++)
    newst[i] |= (st[i + 1] & No[i]);
}
 
inline void move_South()
{
  for(int i = 1; i < r; i ++)
    newst[i] |= (st[i - 1] & S[i]);
}
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> r >> c >> m;
  for(int i = 0; i < r; i++)
    cin >> s[i];
  string dir;
  cin >> dir;
 
  for(int i = 0; i < r; i ++)
    for(int j = 0; j < c; j++)
      if(s[i][j] == '.')
	{
	  st[i][j] = true;
	  if(j > 0 && s[i][j-1] == '.')
	    W[i][j - 1] = true;
	  if(j + 1 < c && s[i][j+1] == '.')
	    E[i][j + 1] = true;
	  if(i > 0 && s[i-1][j] == '.')
	    No[i-1][j] = true;
	  if(i + 1 < r && s[i+1][j] == '.')
	    S[i+1][j] = true;
	}
  
  for(int i = 0; i < m; i ++)
    {
      
      if(dir[i] == 'N' || dir[i] == '?')
	move_North();
      if(dir[i] == 'S' || dir[i] == '?')
	move_South();
      if(dir[i] == 'E' || dir[i] == '?')
	move_East();
      if(dir[i] == 'W' || dir[i] == '?')
	move_West();
      update();
    }
  
  int ans = 0;
  for(int i = 0; i < r; i++)
    ans += st[i].count();
  cout << ans << endl;
  return 0;
}

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