Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.06.2021, 22:50   #1
canadamoscow
Пользователь
 
Аватар для canadamoscow
 
Регистрация: 16.05.2020
Сообщений: 57
По умолчанию Сгенерировать лабиринт. Проход по лабиринту (поиск кратчайшего пути в матрице)

Сгенерировать матрицу m x n (задается пользователем) состоящую из 0 и 1. 0 - это стена, 1 - это проход.
Найти оптимальный проход из точки (0,0) (старт) в точку (m-1,n-1) (финиш.- правый нижний угол)
Вывести на экран сгенерированную матрицу, и правее матрицу кратчайшего пути следования из точки старта (1,1) в точку финиша (m, n) обозначить клетки пути '*', пустые клетки '_' как в примере:

Введите m и n через пробел: 10 12
1 0 0 1 1 1 1 1 1 1 1 1 ... * 0 0 _ * * * * _ _ _ _
1 1 1 1 1 0 1 1 0 1 0 1 ... * * * * * 0 _ * 0 _ 0 _
1 1 0 0 0 1 1 1 1 1 1 1 ... _ _ 0 0 0 _ _ * _ _ _ _
0 0 1 0 1 1 0 1 1 1 0 1 ... 0 0 _ 0 _ _ 0 * _ _ 0 _
1 1 1 1 1 1 1 1 0 0 0 1 ... _ _ _ _ _ _ * * 0 0 0 _
1 0 1 1 0 0 1 1 0 0 1 0 ... _ 0 _ _ 0 0 * _ 0 0 _ 0
0 0 1 0 1 1 1 1 1 1 1 0 ... 0 0 _ 0 _ _ * _ _ _ _ 0
1 1 1 1 1 1 1 1 1 0 0 0 ... _ _ _ _ _ _ * _ _ 0 0 0
1 1 0 0 0 0 1 0 0 1 1 1 ... _ _ 0 0 0 0 * 0 0 * * *
0 0 0 0 1 1 1 1 1 1 0 1 ... 0 0 0 0 _ _ * * * * 0 *

Последний раз редактировалось canadamoscow; 07.06.2021 в 22:55.
canadamoscow вне форума Ответить с цитированием
Старый 07.06.2021, 22:56   #2
canadamoscow
Пользователь
 
Аватар для canadamoscow
 
Регистрация: 16.05.2020
Сообщений: 57
По умолчанию

На PascalABC.net:
Код:
var (m,n) := ReadlnInteger2('Введите m и n через пробел:');
var a := MatrGen(m,n, (i,j) -> round(abs(sin(i+j/Random(1,5))))); //генерация матрицы
var d := MatrFill(m,n, 999); //дистанция от финиша (999=бесконечность)

Procedure dplus(i,j: integer); //заполнение матрицы d
begin
  forEach var (di,dj) in ||0,-1|,|0,1|,|1,0|,|-1,0|| do begin
    var (u,v) := (i+di, j+dj);//слева, справа, снизу, сверху
    if (u in 0..m-1) and (v in 0..n-1) and (a[u,v]=1) and (d[u,v] > d[i,j]+1) then
     begin
        d[u, v] := d[i, j] + 1; 
        dplus(u,v);
     end;
  end;   
end;

begin
  a[0,0] := 1; a[m-1,n-1] := 1; //после генерации лабиринта, открываем концы пути
  var acopy := copy(a); //запоминаем для вывода на экран
  d[m-1, n-1] := 0; //клетка финиша, дистанция от финиша = 0 клеток
{}dplus(m-1,n-1); //заполняем матрицу дистанций от финишной клетки         
  a[0,0] := 8; //помечаем '8' первую клетку пути
  var (u,v) := (0,0); //строим маршрут от старта к финишу
  var next := d[0,0]-1; //след.шаг на 1 ближе к офинишу
  if next <> 998 then //если маршрут существует то строим его в матрице a
   repeat
     forEach var (uu,vv) in ||0,-1|,|0,1|,|1,0|,|-1,0|| do //поиск след.клетки/шага
         if (u+uu in 0..m-1) and (v+vv in 0..n-1) and (d[u+uu, v+vv] = next) then 
          (u,v) := (u+uu, v+vv); //индекс следующей клетки пути
     a[u,v] := 8; //помечаем '8' путь на матрице a
     next -= 1; 
   until next = -1;
  var b := a.ConvertAll(t-> t=8 ? '*' : t=1 ? '_' : '0'); //вторая матрица на вывод
  for var i := 0 to m-1 do begin
     acopy.Row(i).Print; Print('   '); b.Row(i).Println(' ') end;
//  d.ConvertAll(t-> t=999 ? '**' : (' '+t).PadLeft(2)).Println(3);//матрица d наглядно
end.
canadamoscow вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение кратчайшего пути по матрице, или передвижение привидений в игре Пакмен Андрей! Общие вопросы C/C++ 0 02.11.2012 21:41
создание графа по матрице и поиск кратчайшего пути из одного графа в другой lexflax Общие вопросы C/C++ 1 06.09.2012 07:32
Поиск кратчайшего пути в графе BaceK Помощь студентам 0 18.12.2011 11:49
поиск кратчайшего пути LENA_M Общие вопросы C/C++ 0 29.05.2010 22:15