Задача о кубике, Перемещение игральной кости Опции

[LammerzAttack]

Вот такая интересная задача:
Имя входного файла: dice.in
Имя выходного файла: dice.out
Количество тестов: 15
Ограничение по памяти: 1 Мб
Ограничение по времени: 1 с

На клетчатом поле размером MxN в левом нижнем углу лежит игральная кость. За один ход ее можно перекатить на клетку вправо или вверх. Стоимостью пути называется сумма чисел на верхней грани кубика во всех клетках пути. Найдите минимальную стоимость пути в правый верхний угол.

Формат входного файла
В первой строке два натуральных числа N и M <= 1000 — размеры доски. Во второй строке три числа от 1 до 6 — числа на верхней, левой и передней грани кубика соответственно (сумма чисел на противоположных гранях кубика равна 7).

Формат выходного файла
Одно натуральное число — минимальная стоимость искомого пути.

Пример
dice.in
5 5
1 4 5

dice.out
29

Помогите с решением.

[virt]

эта задача была то ли на россии ,то ли на каких то сборах ,завтра постараюсь выложить решение.

[LammerzAttack]

эта задача была то ли на россии ,то ли на каких то сборах ,завтра постараюсь выложить решение.

Если выложишь, то спасибо!!!!!

[Digitalator]

Задача децкая, решаеться динамическим программированием.

В оригинале кубик лежит не в углу, как наказаанный, а в какой-то клетке доски, задаваемой координатами. И прийти ему тож надо в клетку, задаваемую координатами.

Решение можно найти в нете.

ЗЫ: у меня был код, да затерялся в гигабайтах фрагменированого NTFS

[virt]

Код

var a:array[1..1000,1..1000]of integer;
   i,j,n,m:integer;
   v,b,p:integer;

function sled(i,j:integer):integer;
begin
....
end;
..............
  read(n,m);
  read(v,b,p);
  a[n,1]:=v;
  for i:=n-1 downto 1 do
     a[i,1]:=a[i+1,1]+sled(i,1);
  for j:=2 to m do
     a[n,j]:=a[n,j-1]+sled(1,j);
  for i:=n-1 downto 1 do
     for j:=2 to m do
        if a[i,j-1]+sled(i,j-1) < a[i+1,j]+sled(i+1,j) then
           a[i,j]:=a[i,j-1]+sled(i,j-1) else a[i,j]:=a[i+1,j]+sled(i+1,j);
......

общий алгоритм очень прост.
функция sled выдает число которое будет на верхней грани.

[LammerzAttack]

Код

var a:array[1..1000,1..1000]of integer;
   i,j,n,m:integer;
   v,b,p:integer;

function sled(i,j:integer):integer;
begin
....
end;
..............
  read(n,m);
  read(v,b,p);
  a[n,1]:=v;
  for i:=n-1 downto 1 do
     a[i,1]:=a[i+1,1]+sled(i,1);
  for j:=2 to m do
     a[n,j]:=a[n,j-1]+sled(1,j);
  for i:=n-1 downto 1 do
     for j:=2 to m do
        if a[i,j-1]+sled(i,j-1) < a[i+1,j]+sled(i+1,j) then
           a[i,j]:=a[i,j-1]+sled(i,j-1) else a[i,j]:=a[i+1,j]+sled(i+1,j);
......

общий алгоритм очень прост.
функция sled выдает число которое будет на верхней грани.

Не понял, как делать функцию sled, и как считать сумму.

Сообщение отредактировано: LammerzAttack - 15.03.2005 2:53

[virt]

ну а сам то подумай как sled реализовать ,определи например несколько состояний ,так что при переходе состояния однозначно меняются. Каждое состояние показавает какая цифра наверху ,и какая будет далешь ,и т.д.

ответ хранится в a[1,m] ::

Код

writeln(a[1,m]);

[madrabbit]

вот я написал пограммку.
вроде работает, нО(!):
чтение не из файла(не умею), и напиано при помощи рекурсии(только это и умею), ну и короче посмотри, может алгоритм поможет чем-нибудь...

Код

Program Dice;
uses crt;
type
   line=array[1..300] of shortint;
   matrix=array[1..6] of shortint;
var
       NN,MM,limit,k:integer;
       mass:matrix;
       lin:line;
procedure dices(masss:matrix;direct:char;n,m,turn:integer;way:line);

begin
if (n>NN) or (m>MM) or (turn>=limit) then exit
         else
            if n+m=NN+MM then begin
                                writeln('gotcha');
                                limit:=turn;  {на данный момент наименьшая сумма  верхних граней}
                                writeln(turn);
                                for k:=1 to n+m do
                                write(way[k],' ');
                                readln;
                                exit
                              end;

            if direct='r' then {так кубик вращается вправо}
                 begin
                 k:=masss[5];
                 masss[5]:=masss[4];
                 masss[4]:=masss[3];
                 masss[3]:=masss[2];
                 masss[2]:=k;
                 n:=n+1        {позиция кубика по горизонтали}
                 end
            else
            if direct='u' then {так кубик вращается вверх}
               begin
               k:=masss[6];
               masss[6]:=masss[2];
               masss[2]:=masss[1];
               masss[1]:=masss[4];
               masss[4]:=k;
               m:=m+1         {позиция кубика по вертикали}
               end;
                       way[n+m]:=masss[2]; {промежуточный путь кубика в виде массива значений верхних  граней}



                       dices(masss,'u',n,m,turn+masss[2],way);
                       dices(masss,'r',n,m,turn+masss[2],way);
end;


BEGIN
clrscr;
writeln('ўўҐ¤ЁвҐ N');
readln(NN);
writeln('ўўҐ¤ЁвҐ M');
readln(MM);
limit:=(NN+MM)*5; {типа первый предел суммы, от фоная}
for k:=1 to 200 do
   lin[k]:=0;           {массив ходов}
writeln('ўўҐ¤ЁвҐ front');
readln(mass[1]);     {это сам кубик}
writeln('ўўҐ¤ЁвҐ up');
readln(mass[2]);     {это сам кубик}
writeln('ўўҐ¤ЁвҐ right');
readln(mass[3]);     {это сам кубик}
mass[4]:=7-mass[2]; {это сам кубик}
mass[5]:=7-mass[3];  {это сам кубик}
mass[6]:=7-mass[1];   {это сам кубик}
dices(mass,'0',0,0,0,lin);
writeln('Done!');
readln
END
.

очень буду рад предложения по поводу того, как реализовать мою программу(если такое возможно) с требуемыми условиями задачи...
спасибо.

[virt]

Код

Program Dice;
uses crt;
type
  line=array[1..300] of shortint;
  matrix=array[1..6] of shortint;
var
      NN,MM,limit,k:integer;
      mass:matrix;
      lin,way:line;

procedure dices(masss:matrix;direct:char;n,m,turn:integer);
begin
  if (n<1) or (m>MM) or (turn>=limit) then exit
     else
        if (nn-n+1)+m=NN+MM then
           begin
              limit:=turn;  {на данный момент наименьшая сумма  верхних граней}
              lin:=way;
              exit;
           end;
  if direct='r' then {так кубик вращается вправо}
     begin
        k:=masss[5];
        masss[5]:=masss[4];
        masss[4]:=masss[3];
        masss[3]:=masss[2];
        masss[2]:=k;
     end else
               if direct='u' then {так кубик вращается вверх}
                  begin
                     k:=masss[6];
                     masss[6]:=masss[2];
                     masss[2]:=masss[1];
                     masss[1]:=masss[4];
                     masss[4]:=k;
                  end;
  way[(nn-n)+m]:=masss[2]; {промежуточный путь кубика в виде массива значений верхних  граней}
  dices(masss,'u',n-1,m,turn+masss[2]);
  dices(masss,'r',n,m+1,turn+masss[2]);
end;


BEGIN
  clrscr;
  writeln('ўўҐ¤ЁвҐ N');   readln(NN);
  writeln('ўўҐ¤ЁвҐ M');   readln(MM);
  limit:=maxint; {типа первый предел суммы, от фоная}
  for k:=1 to 300 do
     lin[k]:=0;           {массив ходов}
  way:=lin;
  writeln('ўўҐ¤ЁвҐ front');  readln(mass[1]);     {это сам кубик}
  writeln('ўўҐ¤ЁвҐ up');     readln(mass[2]);     {это сам кубик}
  writeln('ўўҐ¤ЁвҐ right');  readln(mass[3]);     {это сам кубик}
  mass[4]:=7-mass[2]; {это сам кубик}
  mass[5]:=7-mass[3];  {это сам кубик}
  mass[6]:=7-mass[1];   {это сам кубик}
  dices(mass,'0',nn,1,0);
  readln;
END.

так вроде лучше.

[madrabbit]

так вроде лучше.

ага, спасибо, вроде смотрю-правильно, а тест не работает... в чем ошибка
и 1000*1000 не получается-переполнение стека, че делать...

[volvo]

1000*1000 не получается-переполнение стека, че делать...

:D Любимая ошибка?
Ну, можешь увеличить размер под стек (первой строкой программы):

Код

{$M 65520, 0, 0}

Только при 1000х1000 программа будет очень долго выполняться (если этот алгоритм вообще приведет к решению)

[virt]

volvo,
должен привести ,это полный перебор.