#lang racket

(define (построить-путь-в-лабиринте заблокированные-ячейки start finish DIM)
  
  (define (соседи place)
    (let ((x (car place))
          (y (cdr place))
          (in_frame? (lambda (s) (let ((p (car s)) (q (cdr s)))
                       (and (>= p 1) (<= p DIM) (>= q 1) (<= q DIM))))))
      (filter in_frame?
              (list (cons (+ x 1) y) (cons (- x 1) y) (cons x (+ y 1)) (cons x (- y 1))))))

  (define (разметить-лабиринт all_marked last_marked)
    (let ((flatten1 (lambda (list-of-list-of-pair)
                      (foldl append '() list-of-list-of-pair))))
      (if (member start last_marked)
          (построить-путь all_marked)
          (if (empty? last_marked)
              #f
              (разметить-лабиринт
               (cons last_marked all_marked)
               (remove* (flatten1 all_marked) (flatten1 (map neighbors last_marked)) ) )))))

  (define (построить-путь marked)
    (let* ((common (lambda (xs ys)
                     (filter (lambda (x) (member x ys)) xs) ))
           (шаг-пути (lambda (возможности начало-пути)
                       (if (empty? (cdr возможности))
                           (cons (car возможности) начало-пути)
                           (cons (car (common возможности (neighbors (car начало-пути)))) начало-пути)))))
    
      (reverse (foldl шаг-пути (list start) (reverse (cdr (reverse marked)))))))
  
  (разметить-лабиринт (list заблокированные-ячейки) (list finish)))

                   

; (построить-путь-в-лабиринте '((2 . 2) (3 . 1)) '(1 . 1) '(2 . 3) 3)
;(построить-путь-в-лабиринте '((1 . 3) (2 . 2)) '(1 . 1) '(2 . 3) 3)
(построить-путь-в-лабиринте '((1 . 3) (2 . 2)) '(1 . 1) '(2 . 4) 4)
;(построить-путь-в-лабиринте '((1 . 3) (2 . 2)) '(1 . 1) '(2 . 10) 100)