Майнкрафтия

@Nekit04 · Регистрация: 20.11.2018

Студворк — интернет-сервис помощи студентам

Мы попали в Майнкрафтию, в которой все состоит из блоков размером 1 * 1 * 1.
Вся страна поделена на одинаковые чанки, по одному Чанка для каждого жителя. Чанк представляет собой параллелепипед размером n * m * k блоков. Автор задачи живет в одном из таких чанков. Некоторые блоки этого Чанка пустые и через них можно пройти, а некоторые заставлены камнем, то есть непроходимыми. Автор сейчас находится в блоке с координатами (1, 1, 1) и ему нужно попасть в блок с координатами (n; m; k).
Соответственно, эти два блока всегда пустые. Автор может переходить в соседний блок, если он пустой. Соседним считается блок, который имеет общую грань с данным, то есть находится в одном из шести направлений: снизу, сверху, слева, справа, сзади, спереди. Выходить за пределы чанка запрещено законами Майнкрафтии.

Определите, за которую наименьшее количество переходов автор может попасть из блока с координатами (1, 1, 1) в блок с координатами (n; m; k).

Первая строка содержит 3 числа n, m, k (1≤n, m, k≤60) - размеры чанка.
В следующей строке находится n * m * k цифр, которые описывают чанк. Если определенное число равное единице, то соответствующий блок пустой, иначе блок является непроходимым.
Номера блоков идут в следующем порядке:
(1, 1, 1), (2, 1, 1), (3, 1, 1) ... (n, 1, 1), (1, 2, 1), (2, 2, 1). .. (n; m; 1), (1, 1, 2), (2, 1, 2) ... (n-1; m; k), (n; m; k).

Выведите наименьшее количество переходов, необходимую для того, чтобы попасть из блока с координатами (1, 1, 1) в блок с координатами (n; m; k).
Гарантируется, что всегда можно добраться из начального в конечный блок.

Выходные данные в формате input.txt:
2 марта 2
0 1 1 1 0 1 0 0 1 0 1 0

Результат работы в файле output.txt:
4

В первом примере автор может двигаться следующему маршруту: (1, 1, 1), (1, 1, 2), (2, 1, 2), (2, 2, 2), (2, 3, 2)

@Mikstereo · 20.11.2018, 23:09

Наименьшее расстояние равняется вектору с вершинами в (x,y,z) и (n,m,k).Пусть (x,y,z) -начальная точка(A),(n,m,k)-последняя точка(B). $https://www.cyberforum.ru/cgi-bin/latex.cgi?\huge A\vec{B}$ ,если нигде не ошибся.Маршрут возможно будет графом,где нужно найти наименьшее расстояние.

@Sun Serega · 21.11.2018, 00:05

Не по теме:

Вообще то, чанки в майнкрафте всегда имеют размер 16*256*16)))

Добавлено через 18 минут
А по теме - у вас в задании что то не так. У вас сказано что 1 это проходимый блок, а 0 это непроходимый. Но если так - в примере входа начало и конец это непроходимые блоки.

Добавлено через 17 минут
Вот программа с расчётом на то, что всё же 0 это пустые блоки, а 1 это камень.

Pascal

begin
  var (w,h,l) := ReadInteger3;
  var can_step := new boolean[w,h,l];
  
  for var i3 := 0 to l-1 do
    for var i2 := 0 to h-1 do
      for var i1 := 0 to w-1 do
        can_step[i1,i2,i3] := ReadInteger=0;
  
  var prev := Lst(new class(
    last_dir := byte(0),
    
    x := 1,
    y := 1,
    z := 1
    
  ));
  
  while true do
  begin
    var curr := prev[prev.Count-1];
    curr.last_dir += 1;
    
    var nx := curr.x;
    var ny := curr.y;
    var nz := curr.z;
    
    if (nx=w) and (ny=h) and (nz=l) then break;
    
    case curr.last_dir of
      1: if nx=w then continue else nx += 1;
      2: if ny=h then continue else ny += 1;
      3: if nz=l then continue else nz += 1;
      4: if nx=1 then continue else nx -= 1;
      5: if ny=1 then continue else ny -= 1;
      6: if nz=1 then continue else nz -= 1;
      else
      begin
        prev.RemoveLast;
        continue;
      end;
    end;
    if prev.Any(pos->(pos.x=nx) and (pos.y=ny) and (pos.z=nz)) then continue;
    
    prev.Add(new class(
      last_dir := byte(0),
      
      x := nx,
      y := ny,
      z := nz
      
    ));
    
  end;
  
  writeln(prev.Count-1);
  
end.

@Nekit04 0 / 0 / 0 Регистрация: 20.11.2018 Сообщений: 7
		1
	Майнкрафтия 20.11.2018, 20:36. Показов 505. Ответов 2 Метки нет (Все метки) Мы попали в Майнкрафтию, в которой все состоит из блоков размером 1 * 1 * 1. Вся страна поделена на одинаковые чанки, по одному Чанка для каждого жителя. Чанк представляет собой параллелепипед размером n * m * k блоков. Автор задачи живет в одном из таких чанков. Некоторые блоки этого Чанка пустые и через них можно пройти, а некоторые заставлены камнем, то есть непроходимыми. Автор сейчас находится в блоке с координатами (1, 1, 1) и ему нужно попасть в блок с координатами (n; m; k). Соответственно, эти два блока всегда пустые. Автор может переходить в соседний блок, если он пустой. Соседним считается блок, который имеет общую грань с данным, то есть находится в одном из шести направлений: снизу, сверху, слева, справа, сзади, спереди. Выходить за пределы чанка запрещено законами Майнкрафтии. Определите, за которую наименьшее количество переходов автор может попасть из блока с координатами (1, 1, 1) в блок с координатами (n; m; k). Первая строка содержит 3 числа n, m, k (1≤n, m, k≤60) - размеры чанка. В следующей строке находится n * m * k цифр, которые описывают чанк. Если определенное число равное единице, то соответствующий блок пустой, иначе блок является непроходимым. Номера блоков идут в следующем порядке: (1, 1, 1), (2, 1, 1), (3, 1, 1) ... (n, 1, 1), (1, 2, 1), (2, 2, 1). .. (n; m; 1), (1, 1, 2), (2, 1, 2) ... (n-1; m; k), (n; m; k). Выведите наименьшее количество переходов, необходимую для того, чтобы попасть из блока с координатами (1, 1, 1) в блок с координатами (n; m; k). Гарантируется, что всегда можно добраться из начального в конечный блок. Выходные данные в формате input.txt: 2 марта 2 0 1 1 1 0 1 0 0 1 0 1 0 Результат работы в файле output.txt: 4 В первом примере автор может двигаться следующему маршруту: (1, 1, 1), (1, 1, 2), (2, 1, 2), (2, 2, 2), (2, 3, 2) 0

@Mikstereo 98 / 36 / 18 Регистрация: 05.11.2018 Сообщений: 231
	20.11.2018, 23:09	2
	Наименьшее расстояние равняется вектору с вершинами в (x,y,z) и (n,m,k).Пусть (x,y,z) -начальная точка(A),(n,m,k)-последняя точка(B). $https://www.cyberforum.ru/cgi-bin/latex.cgi?\huge A\vec{B}$ ,если нигде не ошибся.Маршрут возможно будет графом,где нужно найти наименьшее расстояние. 0

Опции темы