这是一个用最少的代码解决的有趣问题。我预计递归解决方案将最受欢迎。
我们有一个迷宫，它被定义为一张人物地图，其中=是一堵墙，一个空间是一条路径，+是你的起点，#也是你的终点。一个非常简单的例子是这样的：
====
+ =
= ==
= #
====
你能用尽可能少的代码编写一个程序来找到解决这种风格的迷宫的最短路径吗？
如果它适用于所有迷宫输入，例如那些具有跨越自身的路径或具有大量分支的迷宫输入，则可以加分。该程序应该能够适用于大型迷宫（例如，1024x1024 - 1 MB），并且如何将迷宫传递给程序并不重要。
“玩家”可以沿对角线移动。输入迷宫永远不会有对角线通道，因此您的基本动作集将是上、下、左、右。对角线运动只是向前看一点，以确定是否可以合并上/下和左/右。
输出必须是迷宫本身，其中最短路径使用星号字符 ( *) 突出显示。
适用于任何具有最少 CPU 周期的（固定大小）迷宫（假设 BFG2000 足够大）。源大小无关紧要，因为编译器非常高效。
while curr.x != target.x and curr.y != target.y:
case:
target.x > curr.x : dx = 1
target.x < curr.x : dx = -1
else : dx = 0
case:
target.y > curr.y : dy = 1
target.y < curr.y : dy = -1
else : dy = 0
if cell[curr.x+dx,curr.y+dy] == wall:
destroy cell[curr.x+dx,curr.y+dy] with patented BFG2000 gun.
curr.x += dx
curr.y += dy
survey shattered landscape
F#，不是很短（72 行非空行），但可读。我稍微改变/磨练了规格；我假设原来的迷宫是一个完全被墙壁包围的矩形，我使用不同的字符（不会伤害我的眼睛），我只允许正交移动（不是对角线）。我只尝试了一个样本迷宫。除了关于翻转 x 和 y 指标的错误之外，这是第一次工作，所以我认为它是正确的（除了在我给它的一个样本上观察解决方案之外，我没有做任何事情来验证它）。
open System
[<Literal>]
let WALL = '#'
[<Literal>]
let OPEN = ' '
[<Literal>]
let START = '^'
[<Literal>]
let END = '$'
[<Literal>]
let WALK = '.'
let sampleMaze = @"###############
# # # #
# ^# # # ### #
# # # # # # #
# # # #
############ #
# $ #
###############"
let lines = sampleMaze.Split([|'\r';'\n'|], StringSplitOptions.RemoveEmptyEntries)
let width = lines |> Array.map (fun l -> l.Length) |> Array.max
let height = lines.Length
type BestInfo = (int * int) list * int // path to here, num steps
let bestPathToHere : BestInfo option [,] = Array2D.create width height None
let mutable startX = 0
let mutable startY = 0
for x in 0..width-1 do
for y in 0..height-1 do
if lines.[y].[x] = START then
startX <- x
startY <- y
bestPathToHere.[startX,startY] <- Some([],0)
let q = new System.Collections.Generic.Queue<_>()
q.Enqueue((startX,startY))
let StepTo newX newY (path,count) =
match lines.[newY].[newX] with
| WALL -> ()
| OPEN | START | END ->
match bestPathToHere.[newX,newY] with
| None ->
bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1)
q.Enqueue((newX,newY))
| Some(_,oldCount) when oldCount > count+1 ->
bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1)
q.Enqueue((newX,newY))
| _ -> ()
| c -> failwith "unexpected maze char: '%c'" c
while not(q.Count = 0) do
let x,y = q.Dequeue()
let (Some(path,count)) = bestPathToHere.[x,y]
StepTo (x+1) (y) (path,count)
StepTo (x) (y+1) (path,count)
StepTo (x-1) (y) (path,count)
StepTo (x) (y-1) (path,count)
let mutable endX = 0
let mutable endY = 0
for x in 0..width-1 do
for y in 0..height-1 do
if lines.[y].[x] = END then
endX <- x
endY <- y
printfn "Original maze:"
printfn "%s" sampleMaze
let bestPath, bestCount = bestPathToHere.[endX,endY].Value
printfn "The best path takes %d steps." bestCount
let resultMaze = Array2D.init width height (fun x y -> lines.[y].[x])
bestPath |> List.tl |> List.iter (fun (x,y) -> resultMaze.[x,y] <- WALK)
for y in 0..height-1 do
for x in 0..width-1 do
printf "%c" resultMaze.[x,y]
printfn ""
//Output:
//Original maze:
//###############
//# # # #
//# ^# # # ### #
//# # # # # # #
//# # # #
//############ #
//# $ #
//###############
//The best path takes 27 steps.
//###############
//# # #....... #
//# ^# #.# ###. #
//# .# #.# # #. #
//# .....# #. #
//############. #
//# $....... #
//###############
387 个字符
从标准输入获取输入。
import sys
m,n,p=sys.stdin.readlines(),[],'+'
R=lambda m:[r.replace(p,'*')for r in m]
while'#'in`m`:n+=[R(m)[:r]+[R(m)[r][:c]+p+R(m)[r][c+1:]]+R(m)[r+1:]for r,c in[(r,c)for r,c in[map(sum,zip((m.index(filter(lambda i:p in i,m)[0]),[w.find(p)for w in m if p in w][0]),P))for P in zip((-1,0,1,0),(0,1,0,-1))]if 0<=r<len(m)and 0<=c<len(m[0])and m[r][c]in'# ']];m=n.pop(0)
print''.join(R(m))
我曾经为求职面试做过这种事情（这是面试前的编程挑战）
设法让它在某种程度上取得了成功，这是一个有趣的小挑战。