Nautilus

Dana jest kwadratowa mapa rozmiaru $R \times C$, w której część pól jest wolna, a część zablokowana. Statek startuje z pewnego nieznanego pola i wykonuje $M$ ruchów zgodnie z planem podróży (przy czym niektóre ruchy w planie są nieczytelne). Wyznaczyć liczbę pól, na których może się znajdować statek po wszystkich ruchach.

Rozwiązanie standardowe

W podzadaniu 1 wszystkie ruchy są czytelne, wobec tego znając pozycję pola początkowego możemy zrobić symulację w czasie $O(M)$, sprawdzającą, czy podczas trasy statek nie wejdzie na pole zablokowane.

Zatem cały algorytm działa w czasie $O(RCM)$:

const int N = 510, M = 5100;
int r,c,m;
char b[N][N],s[M];
int dr[256],dc[256];

int main() {
  dr['N'] = -1; dc['N'] =  0;
  dr['S'] =  1; dc['S'] =  0;
  dr['W'] =  0; dc['W'] = -1;
  dr['E'] =  0; dc['E'] =  1;

  scanf("%d%d%d",&r,&c,&m);
  REP(i,r) scanf("%s",b[i]);
  scanf("%s",s);

  int ans = 0;

  REP(r0,r) REP(c0,c) {
    int r1=r0, c1=c0;
    bool ok = b[r1][c1] != '#';
    REP(i,m) {
      r1 += dr[s[i]];
      c1 += dc[s[i]];
      if (r1 < 0 || c1 < 0 || r1 >= r || c1 >= c || b[r1][c1] == '#') {
        ok = 0; break;
      }
    }
    if (ok) { ++ans; }
  }
  printf("%d\n", ans);
}

Symulację możemy zrobić też, rozpatrując wszystkie pola jednocześnie. To pozwoli nam obsłużyć ruchy nieczytelne. Przez $dp[i,r,c]$ oznaczymy, czy po wykonaniu $i$ ruchów statek może znajdować się na polu $(r,c)$. Na początek $dp[0,r,c]=1$ dla wszystkich pól wolnych.

Dla $i\geq 1$, aby ustalić czy $dp[i,r,c]=1$ dla wolnego pola $(r,c)$, musimy sprawdzić, czy $dp[i-1,r',c']=1$, gdzie $(r',c')$ jest jednym z pól, z którego statek mógł przejść na $(r,c)$ w $i$-tym ruchu (jeśli ruch jest czytelny, to jest tylko jedno takie pole, a jeśli nie, to są wszyscy czterej sąsiedzi).

Takie rozwiązanie też będzie działać w czasie $O(RCM)$:

  REP(r0,r) REP(c0,c) {
    dp[0][r0][c0] = b[r0][c0] != '#';
  }

  REP(i,m) {
    REP(r0,r) REP(c0,c) {
      int ok = 0;
      if (b[r0][c0] != '#') {
        REP(mo,4) if (s[i] == '?' || s[i] == dirs[mo]) {
          int r1 = r0 - dr[dirs[mo]];
          int c1 = c0 - dc[dirs[mo]];
          if (r1 < 0 || c1 < 0 || r1 >= r || c1 >= c || b[r1][c1] == '#') continue;
          if (dp[i&1][r1][c1]) { ok = 1; }
        }
      }
      dp[(i^1)&1][r0][c0] = ok;
    }
  }

  int ans = 0;
  REP(r0,r) REP(c0,c) {
    ans += dp[m&1][r0][c0];
  }
  printf("%d\n", ans);

Rozwiązanie szybsze

Szybsze rozwiązanie uzyskamy, pakując wiersze naszej tabelki $dp$ w bitsety. Dzięki temu złożoność zmniejszy się o stałą do $O(RCM/32)$:

  REP(r0,r) REP(c0,c) {
    bb[r0][c0] = b[r0][c0] != '#';
  }
  REP(r0,r) {
    dp[0][r0] = bb[r0];
  }

  REP(i,m) {
    int io = i&1, in = io^1;

    REP(r0,r) {
      dp[in][r0].reset();
      if (r0 < r-1 && (s[i] == '?' || s[i] == 'N')) {
        dp[in][r0] |= dp[io][r0+1];
      }
      if (r0 > 0 && (s[i] == '?' || s[i] == 'S')) {
        dp[in][r0] |= dp[io][r0-1];
      }
      if (s[i] == '?' || s[i] == 'E') {
        dp[in][r0] |= dp[io][r0] << 1;
      }
      if (s[i] == '?' || s[i] == 'W') {
        dp[in][r0] |= dp[io][r0] >> 1;
      }
    }

    REP(r0,r) { dp[in][r0] &= bb[r0]; }
  }

  int ans = 0;
  REP(r0,r) REP(c0,c) {
    ans += dp[m&1][r0][c0];
  }
  printf("%d\n", ans);