#lang racket (define (построить-путь-в-лабиринте заблокированные-ячейки откуда куда размерность) (разметить-лабиринт (list заблокированные-ячейки ) откуда размерность (list куда))) (define (разметить-лабиринт all_marked start DIM last_marked) (let* ((in_frame? (lambda (place) (let ((x (car place)) (y (cdr place))) (and (>= x 1) (<= x DIM) (>= y 1) (<= y DIM))))) (neighbors (lambda (place) (let ((x (car place)) (y (cdr place))) (filter in_frame? (list (cons (+ x 1) y) (cons (- x 1) y) (cons x (+ y 1)) (cons x (- y 1))))))) (flatten1 (lambda (list-of-list-of-pair) (let loop ((ls list-of-list-of-pair) (cr '()) (res '())) (if (empty? cr) (if (empty? ls) res (loop (cdr ls) (car ls) res) ) (loop ls (cdr cr) (cons (car cr) res))))))) (if (member start last_marked) (построить-путь DIM all_marked start (list start)) (if (empty? last_marked) #f (разметить-лабиринт (cons last_marked all_marked) start DIM (remove* (flatten1 all_marked) (flatten1 (map neighbors last_marked)) ) ))))) (define (построить-путь DIM marked last_point accum) (let* ((кандидаты (car marked)) (in_frame? (lambda (place) (let ((x (car place)) (y (cdr place))) (and (>= x 1) (<= x DIM) (>= y 1) (<= y DIM))))) (neighbors (lambda (place) (let ((x (car place)) (y (cdr place))) (filter in_frame? (list (cons (+ x 1) y) (cons (- x 1) y) (cons x (+ y 1)) (cons x (- y 1))))))) (common (lambda (xs ys) (filter (lambda (x) (member x ys)) xs) ))) (if (empty? (cddr marked)) (reverse (cons (caar marked) accum)) (let ((next (car (common (neighbors last_point) кандидаты)))) (построить-путь DIM (cdr marked) next (cons next accum)))))) ; (построить-путь-в-лабиринте '((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 . 10) 100)