批處理實現(xiàn)尋找迷宮最短路徑最后由 0000 于 -10-22 14:20(實在不知道怎么分類,就選了其他)其實原來有一個批處理解迷宮的解法,只是這個解法可能會生成一條非常長的路線,因為

rem 判斷大方向，把最可能的方向作為首選，其余按概率排列

因此,這里修改了批處理解迷宮的算法,做了一個尋找最短路徑的解法。注意地圖文件是當(dāng)前目錄下的map.txt

@echo off&setlocal enabledelayedexpansion
set>$&(for /f delims== %%a in ($) do set %%a=)&path %path%&del $
:: 不使用 for /f 直接解析命令輸出，是為了避免開啟新進程影響效率
:: 清潔變量環(huán)境，提升腳本效率
echo %time%
:: 一、自適應(yīng)判斷
(
 rem 二分回溯法判斷迷宮寬度
 set /p .1=
 set $=!.1!#
 for %%a in (128 64 32 16 8 4 2 1) do if !$:~%%a^,1!. NEQ . set /a mx+=%%a&set $=!$:~%%a!
 rem 計算迷宮高度
 for /f %%a in (map.txt) do set /a my+=1
 for /l %%a in (2 1 !my!) do set /p .%%a=
)<map.txt
:: mx、my為迷宮寬、高，.1~.N分別記載迷宮每一行的內(nèi)容
:: 獲取墻對應(yīng)的字符
set 墻=!.1:~0,1!
set /a xx=mx*2+1,yy=my+3
:: 二、收集基本信息
:: nx為寬度減一，用于后面的偏移，all為尋路時的總迭代上限
set /a nx=mx-1,all=10000
:: 確定出入口的位置
set se= 
for /l %%a in (1 1 %my%) do (
 if not !.%%a:~,1!==%墻% set se=!se!0.%%a 
 if not !.%%a:~-1!==%墻% set se=!se!%nx%.%%a 
)
for /l %%a in (0 1 %nx%) do (
 if not !.1:~%%a,1!==%墻% set se=!se!%%a.1 
 if not !.%my%:~%%a,1!==%墻% set se=!se!%%a.%my% 
)
:: 設(shè)置 se 變量中的第一個坐標(biāo)為起點，最后一個坐標(biāo)為終點
for %%a in (!se!) do (
 if defined start (
set end=%%a
 ) else (
set start=%%a
))
:: 三、開始
::反方向
set dir_←=_x+=1
set dir_↑=_y+=1
set dir_→=_x-=1
set dir_↓=_y-=1
:: 從終點開始搜索
set ds= 
set ds1= %end% 
for /l %%a in (1 1 %my%) do set .S%%a=!.%%a!
for /l %%a in (1 1 %all%) do (
 rem 搜索完畢，沒有線路
 if !ds1: =!== goto ok
 set count=%%a
 rem use為上一層迭代的位置(不能后退)
 set use=!ds!
 set ds=!ds1!
 set ds1= 
 for %%b in (!ds!) do (
for /f tokens=1-2 delims=. %%x in (%%b) do (
 for %%c in (← → ↑ ↓) do (
set /a _x=%%x,_y=%%y,!dir_%%c!
for /f tokens=1-2 %%X in (!_x! !_y!) do (
 if defined .%%Y if %%X geq 0 (
if not !.%%Y:~%%X,1!==!墻! if !use!==!use: %%X.%%Y =! (
 rem 標(biāo)記最佳方向
 set /a _x1=%%X+1
 for %%Z in (!_x1!) do set .S%%Y=!.S%%Y:~,%%X!%%c!.S%%Y:~%%Z!
 set use=!use!%%X.%%Y 
 rem 更新下一組搜索點
 set ds1=!ds1!%%X.%%Y 
)
rem 到達(dá)起點
if %%x.%%y==%start% goto ok
))))))
:ok
::正方向
set dir_←=_x-=1
set dir_↑=_y-=1
set dir_→=_x+=1
set dir_↓=_y+=1
for /f tokens=1-2 delims=. %%x in (%start%) do (
 set /a _x=%%x,_y=%%y
)
:: 根據(jù)標(biāo)記來移動繪制點
for /l %%a in (1 1 !count!) do (
 for /f tokens=1-2 %%x in (!_x! !_y!) do (
set _u=!.S%%y:~%%x,1!
if defined dir_!_u! (
 for %%u in (!_u!) do (
set /a _x1=%%x+1
for %%z in (!_x1!) do set .%%y=!.%%y:~,%%x!%%u!.%%y:~%%z!
rem 獲取下一繪制地點
set /a !dir_%%u!
))))
for /l %%a in (1 1 !my!) do echo(!.%%a!
echo %time%
pause
nclick="copycode($('code0'));">復(fù)制代碼

附上原帖的迷宮樣例：

█████████████████████████████
█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓▓
█▓█████▓█████▓█▓▓▓███▓▓██▓▓▓█
█▓▓▓▓▓█▓▓▓▓▓█▓███▓▓▓█▓▓▓█████
███▓█▓█▓███▓▓▓█▓▓▓█▓███▓▓▓▓▓█
█▓▓▓█████▓█████████▓▓▓█████▓█
███▓▓█▓▓▓▓▓▓▓▓▓▓█▓▓▓█▓▓▓▓▓█▓█
█▓██▓█▓██████▓█▓█▓███████▓█▓█
█▓▓▓▓▓▓▓▓▓▓▓███▓█▓▓▓█▓▓▓▓▓█▓█
█▓▓▓█▓██▓██▓▓▓█▓███▓███████▓█
█▓▓▓█▓▓▓▓▓█▓█▓█▓▓▓█▓▓▓▓▓▓▓█▓█
█▓███████▓█▓█████▓█████▓███▓█
█▓▓▓▓█▓▓█▓█▓█▓▓▓▓▓█▓▓▓█▓█▓▓▓█
████▓█▓██▓███▓███████▓█▓███▓█
█▓▓▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█▓▓▓▓█▓▓▓█
██████████▓█▓███▓█▓██▓███▓███
█▓▓▓▓▓▓█▓▓▓▓▓▓▓▓▓█▓▓█▓▓▓█▓▓▓█
█▓████▓█▓█▓███████▓████▓███▓█
█▓▓▓▓█▓███▓█▓▓█▓▓▓▓▓█▓▓▓█▓▓▓█
████▓█▓▓▓█▓██▓█████▓█▓███▓███
▓▓▓▓▓█▓█▓▓▓▓█▓▓▓▓▓▓▓█▓▓▓▓▓▓▓█
█████████████████████████████
nclick="copycode($('code1'));">復(fù)制代碼

不過雖然路徑短了,體積小了,速度也慢了