40代文系社内SEが、AtCoder Beginner Contest 088 D - Grid RepaintingをCommon Lispで解いてみました。
この問題は、けぬす君がスタートからゴールまでたどり着けるかという迷路と、スコアを最大化するという二段構えになっています。
まず、迷路を解かなければならないので、深さ優先探索か幅優先探索が使えそうだと考えました。
次にスコアの最大化について考えると、幅優先探索を選択するべきだと考えました。
通過しなくてよいマスを白から黒に塗り替えることでスコアが得られ、それが最大になるのは最短経路を残して塗り替えたときだからです。
計算量は$O(HW)$です。
以上より、以下の手順で解きます。
- 幅優先探索でスタートからゴールまでたどる。このときにスタートから各マスまでの移動回数を記録する。
- ゴールまでたどり着けないときは、$-1$を出力して処理を終了する。
- ゴールまでたどり着けたときは、グリッド全体の白マスをカウントし、ゴールまでの移動回数を引いた値を出力する。
(require :sb-concurrency)
(let* ((h (read))
(w (read))
(s (make-array h))
(visiting (sb-concurrency:make-queue))
(dist (make-array (list h w) :initial-element nil)))
(loop for i from 0 below h
do (setf (aref s i) (read-line)))
(labels ((bfs ()
(when (not (sb-concurrency:queue-empty-p visiting))
(let ((current (sb-concurrency:dequeue visiting)))
(loop for direction in '((0 . 1) (1 . 0) (0 . -1) (-1 . 0))
for next = (cons (+ (car current) (car direction))
(+ (cdr current) (cdr direction)))
when (and (<= 0 (car next) (1- h))
(<= 0 (cdr next) (1- w))
(char= (char (aref s (car next)) (cdr next)) #\.)
(null (aref dist (car next) (cdr next))))
do (setf (aref dist (car next) (cdr next))
(1+ (aref dist (car current) (cdr current))))
(sb-concurrency:enqueue next visiting))
(bfs)))))
(setf (aref dist 0 0) 0)
(sb-concurrency:enqueue (cons 0 0) visiting)
(bfs)
(let ((count-. (loop for si across s sum (count #\. si)))
(dist-goal (aref dist (1- h) (1- w))))
(format t "~A~%" (if (null dist-goal)
-1
(- count-. (1+ dist-goal)))))))
解法やアルゴリズムで分類した、解いてみたリストはこちらです。
AtCoder Beginner Contestを解いてみたリスト
