abc456_e

by

関連記事

1. 問題

2. コード（WA11）

;; (make-edges 4 '(1 2 1 4 2 4 2 3))
;;=> #(NIL (4 2) (3 4 1) (2) (2 1))
(defun make-edges (N lst)
  (let* ((ary (make-array (1+ N) :element-type 'list
                            :initial-element nil)))
    (loop for (u v) on lst by #'cddr 
          while v
          do
             (push v (aref ary u))
             (push u (aref ary v)))
    ary))

;; (edges->nodes *e* 2) ;=> (3 4 1)
(defun edges->nodes (edges n)
  (aref edges n))

;; (make-holidays 4 3 '("xxo" "xox" "oxo" "oxx")) ;=>
;; #2A((NIL NIL NIL NIL)
;;     (NIL NIL NIL T)
;;     (NIL NIL T NIL)
;;     (NIL T NIL T)
;;     (NIL T NIL NIL))
(defun make-holidays (N W lines)
  (let* ((ary2d (make-array (list (1+ N) (1+ W))
                            :element-type 'boolean
                            :initial-element nil)))
    (loop for city from 1 to N
          for line in lines
          do (loop for day from 1 to W
                   for ch across line
                   do (setf (aref ary2d city day)
                            (eql ch #\o))))
    ary2d))


;; (defparameter *e* (make-edges 4 '(1 2 1 4 2 4 2 3)))
;; (defparameter *h*
;;   (make-holidays 4 3 '("xxo" "xox" "oxo" "oxx")))


(defun cycle (x cycle)
  (1+ (mod (1- x) cycle)))

;; (next-holiday-cities 3 2 3 *e* *h*) ;=> (3 1)
;; (next-holiday-cities 3 2 4 *e* *h*) ;=> (3 4)
;; (next-holiday-cities 3 1 2 *e* *h*) ;=> (2)
(defun next-holiday-cities (W current-city next-day edges holidays)
  (loop for city in (cons current-city
                          (edges->nodes edges current-city))
        when (aref holidays city (cycle next-day W))
          collect city))

;; (holiday-cities 4 3 1 *h*) ;=>  (3 4)
(defun holiday-cities (N W day holidays)
  (loop for city from 1 to N
        when (aref holidays city (cycle day W))
          collect city))

;; (next-cities 3 '(1 2 3 4) 2 *e* *h*) ;=> (2)
;; (next-cities 3 '(2) 3 *e* *h*)       ;=> (3 1)
;; (next-cities 3 '(3 1) 4 *e* *h*)     ;=> (4)
;; (next-cities 3 nil 4 *e* *h*)        ;=> NIL
(defun next-cities (W cities next-day edges holidays)
  (loop for city in cities
        append (next-holiday-cities
                W city next-day edges holidays) into result
        finally (return (remove-duplicates result))))

;; (endless-holiday-p 4 3 *e* *h*) ;=> T
(defun endless-holiday-p (N W edges holidays)
  (loop for day from 2 to (1+ W)
        with current-cities = (holiday-cities N W 1 holidays)
        while current-cities
        do (setf current-cities
                 (next-cities
                  W current-cities day edges holidays))
        finally (return (consp current-cities))))

(defun print-yesno (c)
  (declare (type boolean c))
  (princ (if c "Yes" "No")))

(defun main ()
  (let* ((times (read)))
    (loop repeat times
          for N = (read)
          for M = (read)
          for edge-list = (loop repeat (* M 2)
                                collect (read))
          for W = (read)
          for lines = (loop repeat N
                            collect (read-line))
          for edges = (make-edges N edge-list)
          for holidays = (make-holidays N W lines)
          do (print-yesno (endless-holiday-p
                           N W edges holidays))
             (terpri))))

#-swank(main)Code language: Lisp (lisp)
2. コード（WA11）