4

これは、最小限のコードで解決できる興味深い問題です。再帰的なソリューションが最も人気があると思います。

キャラクターのマップとして定義された迷路があります。ここ=で、 は壁、スペースはパス、+開始点、#終了点です。信じられないほど単純な例は次のようになります。

====
+  =
= ==
=  #
====

できるだけ少ないコードで、このスタイルの迷路を解くための最短経路を見つけるプログラムを作成できますか?

交差するパスや膨大な数の分岐があるものなど、すべての迷路入力で機能する場合はボーナス ポイントです。プログラムは大きな迷路 (たとえば、1024x1024 - 1 MB) で動作できる必要があり、迷路をプログラムに渡す方法は重要ではありません。

「プレイヤー」は斜めに移動することがあります。入力迷路には斜めの通路がないため、基本的な動きのセットは上、下、左、右になります。斜めの動きは、上下と左右がマージできるかどうかを判断するために、少し前を見ているだけです。

出力は、アスタリスク文字 ( ) を使用して強調表示された最短パスを持つ迷路自体である必要があります*。

4

4 に答える 4

8

最小の 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
于 2009-08-25T06:28:32.660 に答える
7

F＃、それほど短くはありませんが（72行の非空白行）、読み取り可能です。スペックを少し変更/磨きました。元の迷路は壁で完全に囲まれた長方形であると想定し、さまざまなキャラクターを使用し（目を傷つけない）、直交する動きのみを許可します（対角線ではありません）。サンプル迷路を1つだけ試しました。xとyのインデックスの反転に関するバグを除いて、これは初めて機能したので、正しいと思います（私が提供した1つのサンプルのソリューションを目で確認する以外に、検証することは何もしていません）。

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.
//###############
//#  # #....... #
//# ^# #.# ###. #
//# .# #.# # #. #
//# .....#   #. #
//############. #
//#    $....... #
//###############
于 2009-08-25T08:04:48.863 に答える
6

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))
于 2009-08-28T19:47:14.487 に答える
0

就職の面接でこのようなことをしたことがあります（面接前のプログラミングの課題でした）

ある程度の成功を収めることができました。これは楽しい小さな挑戦です。

于 2010-03-11T22:36:29.730 に答える