C - Crystal Researcher

概要

少し実装が重ための問題です．

問題原案：@uni_kakurenbo

解説

$Ⅰ.$ 課題の細分化

この問題は大きく以下の二つのパートの分割して解くことができます．

• MojaMoja くんの移動経路$(S)$ から洞窟内の構造を復元するパート
• 復元された洞窟の情報をもとに，水晶が埋蔵されているマスの個数を数え上げるパート

$Ⅱ.$ 方針と実装方法の工夫

$1)$ 復元パート

1. 全体像

MojaMoja 君の辿った経路を実際にシミュレーションすることで，洞窟内の構造を復元してみましょう．
具体的には，はじめ洞窟内はすべて通行不能なマスで埋まっているとして，MojaMoja 君が通った箇所だけを通行可能なマスの置き換えるということをします．

2. 情報の管理

一旦，盤面は $H \times W$ の二次元配列などで管理することにします．
また，MojaMoja 君の行動を再現するために，MojaMoja 君の「位置」と「向き」を，変数で持っておきます．
位置については「グリッドの左上から $i$ 行目，$j$ 列目」のように $2$ 変数 $i, j$ を用いるとよいでしょう．
向きについては「はじめの向き」を $0$ として，右に $90$ 度回転する毎に $(0,)\, 1, 2, 3, 0, 1, 2, ...$ というように $0$ 以上 $4$ 未満の数値で扱うと便利です．
たとえば，はじめの向きを東とすると 東: $0$，南: $1$，西: $2$，北: $3$ のように対応します．ここでは変数 $d$ を用います．

3. 移動の表現

東を向いていたら $j$ を $1$ 増やす，南を向いていたら $i$ を $1$ 増やす，西を向いていたら $j$ を $1$ 減らす，北を向いていたら $i$ を $1$ 減らす...
というように移動を表現することもできますが，少々冗長です．

こういった移動方向の表現に適したテクニックがありますのでご紹介いたします．
「向き $d$ で正面へ $1$ マスだけ進んだときの，$i, j$ の変化」をそれぞれ $\Delta i_d, \Delta j_d$ とすると，
$(\Delta i_d, \Delta j_d) = ((0, 1), (1, 0), (0, -1), (-1, 0) )$ とあらわすことができます．(0-based indexing)
たとえば $(\Delta i_2, \Delta j_2) = (0, -1)$ ですから，向き $2$ で正面(西)へ $1$ マスだけ進むことは $j$ のみを $1$ 減らすことに対応します．

4. 方向転換の表現

$d$ が $0$ 以上 $4$ 未満だということを利用します．
剰余の性質より，右へ $90$ 度回転する動作を $d←(d+1)\%4$ と表現したり，反対に左へ $90$ 度回転する動作を $d←(d-1)\%4$ と表現したりすることができます．

$2)$ 数え上げパート

基本的にはすべてのマスについて隣接する $4$ マスをすべて見るように全探索を行えばよいです．

通行不能なマスのみが対象となることに注意してください．
これをしっかりと実装しないとたとえば次のように左上のマスから移動がなかった場合に結果が変わってしまいます．
これは実装によっては左上のマスにも水晶が埋蔵されているとカウントされてしまうためです．

$$$$$
$.#@$
$#@@$
$@@@$
$$$$$

実際の実装時には奈落の代わりに周囲をさらに通行不能なマスで囲うことで判定が簡単になります．
詳細は「実装例」の項を参照してください．

$Ⅳ.$ 実装

言語によっては被除数の符号が負であるときに % 演算子の返り値も負になることに注意しましょう．
x%y の代わりに (x%y+y)%y を用いたりすることで回避が可能です．

• はじめ，$(i, j, d) = (0, 0, 0)$
• 洞窟の左上から $0$ 行目，$0$ 列目を通行可能なマスで置き換える．
• $S$ の各文字を順々に先頭から参照して
  • その文字が
    • F ならば，$i$ を $\Delta i_d$ 増やし，$j$ を $\Delta j_d$ 増やし，洞窟の左上から $i$ 行目，$j$ 列目を通行可能なマスで置き換える．
    • R ならば，$d$ を $(d+1)\%4$ で置き換える．
    • L ならば，$d$ を $(d-1)\%4$ で置き換える．
    • T ならば，$d$ を $(d+2)\%4$ で置き換える．
• カウンターを $0$ にする
• 洞窟のすべての通行不能なマスについて
  • 隣接する $4$ マスすべてが通行不能なマスならば，カウンターの値を $1$ 増やす．

$Ⅴ.$ 時間計算量

• シミュレーションに $O(N)$
• 数え上げに $O(HW)$

全体で $O(HW+N)$ です．

$Ⅵ.$ 発展

$1)$ 類題

(難易度順)

• ABC 244 $\hspace{0.15em}$ B - Go Straight and Turn Right
• ABC 107 $\hspace{0.15em}$ B - Grid Compression
• ABC 241 $\hspace{0.15em}$ C - Connect 6

実装例

xxxxxxxxxx

#include <bits/stdc++.h>

using namespace std;

​

int main() {

    int H, W, N; cin >> H >> W >> N;

    string S; cin >> S;

​

    vector grid(H+2, vector<int> (W+2, 1));

​

    int di[4] = { 0, 1, 0, -1 }, dj[4] = { 1, 0, -1, 0 };

​

    {

        int i=1, j=1, d=0;

        for(char s : S) {

            grid[i][j] = false;

            if(s == 'F') i += di[d], j += dj[d];

            if(s == 'L') --d;

            if(s == 'R') ++d;

            if(s == 'T') ++++d;

            d = (d+4)%4;

        }

        grid[i][j] = false;

    }

​

    int ans = 0;

    for(int i=1; i<=H; ++i) for(int j=1; j<=W; ++j) {

        if(!grid[i][j]) continue;

        short cnt = 0;

        for(int d=0; d<4; ++d) if(grid[i+di[d]][j+dj[d]]) ++cnt;

        ans += cnt == 4;

    }

​

    cout << ans << "\n";

​

    return 0;

}

xxxxxxxxxx

from itertools import product

​

H, W, N = map(int, input().split())

S = input()

​

H += 2; W += 2

grid = [[1] * W for _ in [0] * H]

​

dis, djs = (0, 1, 0, -1), (1, 0, -1, 0)

​

i, j, d = 1, 1, 0;

for s in S:

    grid[i][j] = 0

    if s == 'F': i += dis[d]; j += djs[d]

    if s == 'L': d = (d-1)%4

    if s == 'R': d = (d+1)%4

    if s == 'T': d = (d+2)%4

grid[i][j] = 0

​

ans = 0

for i, j in product(range(1, H-1),range(1, W-1)):

    if not grid[i][j]: continue

    ans += all(grid[i+di][j+dj] for di, dj in zip(dis,djs))

​

print(ans)