提出 #4572433

---

ソースコード 拡げる

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (terminate-char #\Space))
  "Note that the returned string will be reused."
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let ((,buffer (load-time-value (make-string ,buffer-size
                                                  :element-type 'base-char))))
       (declare (simple-base-string ,buffer)
                (inline read-byte))
       (loop for ,character of-type base-char =
                #-swank (code-char (read-byte ,in nil #.(char-code #\Newline)))
                #+swank (read-char ,in nil #\Newline)
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (when (< ,idx ,buffer-size)
                       (setf (schar ,buffer ,idx) ,terminate-char))
                     (return (values ,buffer ,idx))))))

(defstruct (queue (:constructor make-queue
                    (&optional list &aux (tail (last list)))))
  (list nil :type list)
  (tail nil :type (or null (cons t null))))

(declaim (inline enqueue))
(defun enqueue (obj queue)
  (symbol-macrolet ((list (queue-list queue))
                    (tail (queue-tail queue)))
    (if (null list)
        (setf tail (list obj)
              list tail)
        (setf (cdr tail) (list obj)
              tail (cdr tail))))
  queue)

(declaim (inline dequeue))
(defun dequeue (queue)
  (pop (queue-list queue)))

(declaim (inline enqueue-front))
(defun enqueue-front (obj queue)
  (symbol-macrolet ((list (queue-list queue))
                    (tail (queue-tail queue)))
    (if (null list)
        (setf tail (list obj)
              list tail)
        (push obj list))
    queue))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 4 7 8 15 16 31 32 62 63 64)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

;; Hauptteil
(defun reachable-p (plan start-i start-j)
  "0-1 BFS"
  (declare #.OPT
           ((simple-array base-char (* *)) plan))
  (let* ((height (array-dimension plan 0))
         (width (array-dimension plan 1))
         (height-1 (- height 1))
         (width-1 (- width 1))
         (queue (make-queue))
         (marked (make-array (list height width) :element-type 'bit :initial-element 0)))
    (declare (uint16 height width))
    (labels ((frob-neighbor (dist i j)
               (declare (uint32 dist))
               (case (aref plan i j)
                 (#\#
                  (enqueue (list (1+ dist) i j) queue)
                  (setf (aref marked i j) 1))
                 (#\.
                  (enqueue-front (list dist i j) queue)
                  (setf (aref marked i j) 1))
                 (#\g (return-from reachable-p t)))))
      (declare (inline frob-neighbor))
      (enqueue (list 0 start-i start-j) queue)
      (setf (aref marked start-i start-j) 1)
      (loop for vertex = (dequeue queue)
            until (null vertex)
            for (dist i j) of-type (uint4 uint16 uint16) = vertex
            when (<= dist 2)
            do (when (and (< 0 i) (zerop (aref marked (- i 1) j)))
                 (frob-neighbor dist (- i 1) j))
               (when (and (< i height-1) (zerop (aref marked (+ i 1) j)))
                 (frob-neighbor dist (+ i 1) j))
               (when (and (< 0 j) (zerop (aref marked i (- j 1))))
                 (frob-neighbor dist i (- j 1)))
               (when (and (< j width-1) (zerop (aref marked i (+ j 1))))
                 (frob-neighbor dist i (+ j 1)))
            finally (return nil)))))

(defun main ()
  (declare #.OPT)
  (let* ((height (read))
         (width (read))
         (stadtplan (make-array (list height width) :element-type 'base-char))
         start-i start-j)
    (dotimes (i height)
      (let ((row (buffered-read-line 500)))
        (dotimes (j width)
          (when (char= #\s (aref row j))
            (setf start-i i start-j j))
          (setf (aref stadtplan i j) (aref row j)))))
    (write-line (if (reachable-p stadtplan start-i start-j)
                    "YES" "NO"))))

#-swank(main)

提出情報

ジャッジ結果