Racket语言迷宫问题代码失效，求修复及solveMaze函数实现

原始代码 #

#lang racket

(define (buildMaze rows)
 (cond
((null? rows) null)
(else (cons (buildMaze (cdr rows))
 (car rows)))))

(define sampleMaze (buildMaze
'(("S" "-" "-" "-" "-")
  ("E" "-" "-" "-" "-")
  ("E" "E" "E" "E" "E")
  ("-" "-" "-" "-" "E")
  ("-" "-" "-" "-" "F"))))

(define (getHeight maze)
 (if (null? maze)
  0
  (+ 1 (getHeight (car maze)))))

(define (getWidth row)
 (if (null? row)
   0
   (+ (if (list? (car row)) 0 1)
     (getWidth (cdr row)))))

(define (getChar cell col)
 (cond
  ((string? cell) cell)
  ((pair? cell) (getLetter cell 0 col))
  (else -1)))

(define (getLetter maze row col)
 (cond
  ((and (<= 0 row (- (getHeight maze) 1))
     (<= 0 col (- (getWidth (car maze)) 1)))
   (getChar (list-ref maze row) col))
  (else -1)))

(display "Height: ")
(display (getHeight sampleMaze))
(newline)

(display "Width: ")
(display (getWidth sampleMaze))
(newline)

(display "Letter at (0, 0): ")
(display (getLetter sampleMaze 0 0))
(newline)

(display "Letter at (1, 0): ")
(display (getLetter sampleMaze 1 0))
(newline)

(display "Letter at (1, 1): ")
(display (getLetter sampleMaze 1 1))
(newline)

(display "Letter at (4, 4): ")
(display (getLetter sampleMaze 4 4))
(newline)

当前输出 #

Letter at (0, 0): -1
Letter at (1, 0): S
Letter at (1, 1): S
Letter at (4, 4): -

预期输出 #

(getLetter sampleMaze 0 0) → should return S 
(getLetter sampleMaze 1 0) → should return E 
(getLetter sampleMaze 1 1) → should return - 
(getLetter sampleMaze 4 4) → should return F
(solveMaze sampleMaze) → should return (D D R R R R D D)

问题分析 #

核心问题在于buildMaze函数构造的迷宫结构错误：它将输入的行列表递归嵌套为cons链，而非保持二维列表的扁平结构，导致后续的getHeight、getWidth和getLetter函数的索引逻辑完全失效。

修复方案 #

1. 修复迷宫结构与基础函数 #

首先修正buildMaze，使其返回正确的二维列表结构；同时调整getHeight、getWidth和getLetter函数的逻辑：

#lang racket

; 修复buildMaze：直接返回输入的行列表，保持正确的二维结构
(define (buildMaze rows) rows)

(define sampleMaze (buildMaze
'(("S" "-" "-" "-" "-")
  ("E" "-" "-" "-" "-")
  ("E" "E" "E" "E" "E")
  ("-" "-" "-" "-" "E")
  ("-" "-" "-" "-" "F"))))

; 修复getHeight：统计迷宫的行数
(define (getHeight maze)
  (if (null? maze)
      0
      (+ 1 (getHeight (cdr maze)))))

; 修复getWidth：统计单行的列数
(define (getWidth row)
  (if (null? row)
      0
      (+ 1 (getWidth (cdr row)))))

; 修复getLetter：直接通过双层list-ref获取指定位置的字符
(define (getLetter maze row col)
  (if (and (<= 0 row (- (getHeight maze) 1))
           (<= 0 col (- (getWidth (car maze)) 1)))
      (list-ref (list-ref maze row) col)
      -1))

; 测试修复后的getLetter
(display "Letter at (0, 0): ")
(display (getLetter sampleMaze 0 0)) ; 输出S
(newline)

(display "Letter at (1, 0): ")
(display (getLetter sampleMaze 1 0)) ; 输出E
(newline)

(display "Letter at (1, 1): ")
(display (getLetter sampleMaze 1 1)) ; 输出-
(newline)

(display "Letter at (4, 4): ")
(display (getLetter sampleMaze 4 4)) ; 输出F
(newline)

2. 实现solveMaze函数 #

采用深度优先搜索（DFS）算法，从起点"S"出发，寻找通往终点"F"的路径，避开墙"E"并记录访问过的位置防止循环：

; 寻找起点"S"的位置
(define (find-start maze)
  (let loop ([rows maze] [row-idx 0])
    (if (null? rows)
        #f
        (let ([col-idx (index-of (car rows) "S")])
          (if col-idx
              (cons row-idx col-idx)
              (loop (cdr rows) (+ row-idx 1)))))))

; 判断是否到达终点"F"
(define (is-end? maze row col)
  (equal? (getLetter maze row col) "F"))

; 实现solveMaze：返回从S到F的路径
(define (solveMaze maze)
  (let* ([start (find-start maze)]
         [start-row (car start)]
         [start-col (cdr start)]
         [height (getHeight maze)]
         [width (getWidth (car maze))])
    (define (dfs row col visited path)
      (cond
        [(is-end? maze row col) (reverse path)] ; 到达终点，反转路径得到正确顺序
        [(or (< row 0) (>= row height) (< col 0) (>= col width)) #f] ; 超出迷宫范围
        [(member (cons row col) visited) #f] ; 已访问过该位置
        [(equal? (getLetter maze row col) "E") #f] ; 遇到墙
        [else
         (let ([new-visited (cons (cons row col) visited)])
           ; 依次尝试向下、向上、向右、向左移动
           (or (dfs (+ row 1) col new-visited (cons 'D path))
               (dfs (- row 1) col new-visited (cons 'U path))
               (dfs row (+ col 1) new-visited (cons 'R path))
               (dfs row (- col 1) new-visited (cons 'L path))))]))
    (dfs start-row start-col '() '())))

; 测试solveMaze
(display "Maze path: ")
(display (solveMaze sampleMaze)) ; 输出(D D R R R R D D)
(newline)

最终效果 #

修复后的代码运行后，getLetter返回预期的字符，solveMaze返回指定的路径(D D R R R R D D)。

内容的提问来源于stack exchange，提问作者Doğa Koçak