;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (inline warshall-floyd!))
(defun warshall-floyd! (matrix)
  (let ((n (array-dimension matrix 0)))
    (dotimes (k n)
      (let ((base-k (array-row-major-index matrix k 0)))
        (dotimes (i n)
          (let ((base-i (array-row-major-index matrix i 0)))
            (dotimes (j n)
              (setf (row-major-aref matrix (+ base-i j))
                    (min (row-major-aref matrix (+ base-i j))
                         (+ (row-major-aref matrix (+ base-i k))
                            (row-major-aref matrix (+ base-k j)))))))))))
  matrix)

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(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 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defconstant +inf+ #xffffffff)
(defun main ()
  (declare #.OPT)
  (let* ((h (read))
         (w (read))
         (plan (make-array (list h w) :element-type 'bit :initial-element 0))
         (mat (make-array (list (* h w) (* h w))
                          :element-type 'uint32
                          :initial-element +inf+)))
    (declare (uint8 h w))
    (dotimes (i h)
      (let ((line (read-line)))
        (dotimes (j w)
          (when (char= #\# (aref line j))
            (setf (aref plan i j) 1)))))
    (labels ((encode (y x)
               (+ x (* y w)))
             (connect (y1 x1 y2 x2)
               (when (and (<= 0 y2 (- h 1))
                          (<= 0 x2 (- w 1))
                          (zerop (aref plan y2 x2)))
                 (let ((v1 (encode y1 x1))
                       (v2 (encode y2 x2)))
                   (setf (aref mat v1 v2) 1)))))
      (dotimes (i h)
        (dotimes (j w)
          (when (zerop (aref plan i j))
            (setf (aref mat (encode i j) (encode i j)) 0)
            (connect i j (- i 1) j)
            (connect i j (+ i 1) j)
            (connect i j i (- j 1))
            (connect i j i (+ j 1)))))
      (warshall-floyd! mat)
      (let ((res 0))
        (declare (uint31 res))
        (dotimes (y1 h)
          (dotimes (x1 w)
            (dotimes (y2 h)
              (dotimes (x2 w)
                (when (and (zerop (aref plan y1 x1))
                           (zerop (aref plan y2 x2)))
                  (let ((dist (aref mat (encode y1 x1) (encode y2 x2))))
                    (when (< dist +inf+)
                      (setq res (max res dist)))))))))
        (println res)))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    ;; (run-program "C:/Windows/System32/WindowsPowerShell/v1.0/powershell.exe" '("get-clipboard") :output out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3 3
...
...
...
"
    "4
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3 5
...#.
.#.#.
.#...
"
    "10
")))


Measured memory_bytes: 28384