hacsoft
Junior Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
KapralBel
Спасибо за код разыменования переменной, все бился, как это сделать (в функции обрабатывается переданный ей массив по ссылке).
Задача: Лабиринт
Классическая задача на нахождение кратчайшего пути из т. B в т. E. Вот на досуге решил ее средствами командных файлов. В файле input.txt должна лежать карта лабиринта. Пример:
Код: 0000000000
1111111110
0000100100
0100100100
0100100000
0100000100
0000100110
0000100100
0110110000
0010100000 |
- Лабиринт 10x10 (1 - стена, 0 - проход, за границы карты выйти нельзя).
А вот решение (код немного большой):
Код: ::::::::::::::::::::::::::::::::::::::::::::::
:: Задача нахождения кратчайшего пути ::
:: Решение: Акатов Алексей, HACSoft, 2005 ::
::::::::::::::::::::::::::::::::::::::::::::::
echo off
title Labirint
setlocal enabledelayedexpansion
cls
set bi=2
set bj=0
set ei=5
set ej=6
call :read
echo.
echo Please wait...
set /a min=-%width%*%height%
call :find %bi% %bj% -1
cls
set /a min=-min-1
echo Length = %min%
call :write
goto :eof
::::::::::::::::::::::::::::::::::::::::::::::
:find i j len
:: Поиск пути:
call :get_e %1 %2
if errorlevel %3 if not %errorlevel%==0 exit /b
set lab%1_%2=%3
if %1==%ei% if %2==%ej% set min=%3
set /a len=%3-1
if %len% gtr %min% (
set /a nj=%2+1
call :get_e %1 !nj!
if not errorlevel 1 call :find %1 !nj! %len%
set /a nj=%2-1
call :get_e %1 !nj!
if not errorlevel 1 call :find %1 !nj! %len%
set /a ni=%1+1
call :get_e !ni! %2
if not errorlevel 1 call :find !ni! %2 %len%
set /a ni=%1-1
call :get_e !ni! %2
if not errorlevel 1 call :find !ni! %2 %len%
)
exit /b
:get_e i j
:: Получить значение ячейки lab[i,j]:
if %1 lss 0 exit /b 1
if %1 gtr %height% exit /b 1
if %2 lss 0 exit /b 1
if %2 gtr %width% exit /b 1
exit /b !lab%1_%2!
:write
:: Вывод лабиринта (массива lab) на консоль:
set wall=**
for /l %%j in (0,1,%width%) do set wall=!wall!***
echo %wall%
for /l %%i in (0,1,%height%) do (
set s=
for /l %%j in (0,1,%width%) do (
set a=!lab%%i_%%j!
if %%i==%bi% if %%j==%bj% (set a=[B])
if %%i==%ei% if %%j==%ej% (set a=[E])
if !a!==[B] (set s=!s![B]) else (
if !a!==[E] (set s=!s![E]) else (
if !a!==1 (
set s=!s!***
) else if !a! lss 0 (
set /a a=-a-1
if !a! leq 99 (
set a= !a!
if !a! leq 9 set a= !a!
)
set s=!s!!a!
) else set s=!s!...
))
)
echo *!s!*
)
echo %wall%
exit /b
:read
:: Чтение массива лабиринта lab из файла input.txt:
set height=0
for /f %%s in (input.txt) do call :readline %%s
echo LABIRINT (%height%x%j%):
set /a height-=1
set /a width=j-1
call :write
exit /b
:readline line
:: Чтение одной строки:
set j=0
set s=%1
:nextchar
if not defined s goto nextline
set lab%height%_%j%=%s:~0,1%
set /a j+=1
set s=%s:~1%
goto nextchar
:nextline
set /a height+=1
exit /b |
Переменные bi, bj - координаты начала (считая от 0), а ei, ej - координаты цели, куда мы хотим прийти.
Программа выводит исходный файл, а затем, результат, в котором числами указано количество шагов до текущей ячейки. [B] - точка старта, [E] - точка финиша.
Собственно, поиск пути проходит в рекурсивной функции find, все остальное нужно только для считывания и вывода данных.
P.S. Копируя код через буфер обмена с форума, не забываем удалять пробелы в конце каждой строки, а то может работать не будет. |
