编程高尔夫：解决迷宫问题

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

想要改进这个问题吗？通过编辑这篇文章来更新问题，使其仅关注一个问题。

8 年前已关闭。

Answer 1

适用于具有最少 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

Answer 2

Python

387 个字符

从 stdin 获取输入。

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))

Answer 3

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.
//###############
//#  # #....... #
//# ^# #.# ###. #
//# .# #.# # #. #
//# .....#   #. #
//############. #
//#    $....... #
//###############

Answer 4

我曾经在一次工作面试中做过这样的事情（这是面试前的编程挑战），

设法让它在某种程度上取得成功，这是一个有趣的小挑战。