infoarena

Salut!
I-mi puteti da o idee( algoritmul care trebuie folosit...) despre cum as putea sa rezolv urmatoarea problema:

It is given a chess board with N*N squares. On the board there is a dice with the dimensions
equal with one square on the board and occupies perfectly the surface of a square. On each side of
the dice there is an integer value between 1 and 100.
The dice can move by rotating itself with 90º around one of it`s edge on the board. With this
move it can go in the upper, lower, left and right square. With more moves, the dice can go to each
square on the board. The cost of a path is equal to the sum of the values on the side on the board,
including the first and the last position.
Giving you the dimension of the board N, the six values on the sides of the cube, the starting
position and the final position, find a minimum path from the starting position to the finish one. You
must save in a file the length of the minimum path and the path itself.
Input data: file cube.in
N // board dimension
face back left right up down // the 6 values on the sides of the dice
x1 y1 x2 y2 // the positions of the start and finish squares, with 1 to N numbering
Output data: file cube.out
C // the cost of the minimum path
L // the length of the path, as number of moves of the dice
x1 y1
x2 y2
.....
xL yL // the positions of the squares in the path
Observations: At the start, the cube is positioned with the “face” side in the positive direction of
Oy axis, the “right” side on the positive direction of Ox and the “top” on the positive direction of
Oz.
All the coordinates start from 1.
Limits:
1<=N<=100
Example:
cube.in
8
2 1 1 8 1 1
3 2 4 2

cube.out:
6
6
3 2
3 1
2 1
2 2
3 2
4 2

Pai  mi se  pare  o  problema  de  backtraking...cel  putin asa  stiu sa  o rezolv. Daca  vrei  ma  uit peste grafuri si iti  zic exact :)
Dar  n-am  inteles  ce-s  cu  numerele de  pe  fata  cubului . Tie  iti cere  cel  mai scurt drum  dela  (xi,yi) la  (xf,yf). Ce-s  cu  numerele de pe fata cubului. Sau  iti trebuie cel  mai scrut drum  ca  si cost?

@adrian

Nu e back Nu iti intra cu  tabla de 100 pe 100 cu back. Poti tine o dinamica D[ i ][ j ][ k ] costul minim care se poate obtine ajungand pe linia i, coloana j si cu fata nr k deasupra. Recurenta va fi o(1) si vei avea N ^ 2 * K (k = 6) stari. Indicii i si j vor fi de la x1 y1 la x2 respectiv y2.

O alta metoda, e sa faci un BF din patratul de start, in bf iti vei tine o structura de date care sa retina care sunt indicii patratelului, care e costul minim sa ajungi acolo, si cu ce fata deasupra. Vei introduce un patrat in coada de la BF doar daca nu a mai fost sau daca obtii un cost mai bun. Te opresti cand ai ajuns in patratul de sfarsit.

Spor :)

@alexandru

Numerele de pe fata cubului sunt pentru a obtine costul. Costul se calculeaza in functie de ce fata e deasupra. Asa m-i se pare mie cel putin.

Eu  n-am  inteles daca  trebuie  drumul de cost  minim sau   drumul  minim  pana  la  punctele finale...asta  era dilema  mea:P

I-mi trebuie  drumul de cost  minim.

@alexandru

Drumul de cost minim. Drumul minim se poate calcula (x1 - x2) + (y1 - y2). (E prea simplu)

A reusit sa rezolve cineva problema? Daca da il rog sa-mi spuna si mie cum.
Multumesc anticipat!

Ti-am scris mai sus cum as rezolva-o eu. De unde e problema?

Nu mai gasesc site-ul de pe care am luat problema. Era intr-un pdf pe un blog al unui profesor parca.

La a doua metoda pe care o dai tu, zici ca ma opresc cand am ajuns in patratul de sfarsit, dar in exemplu patratul de start si patratul de sfarsit sunt alaturate deci ma voi opri din prima iar costul va fi 1+8=9 ceea ce nu este ok pentru ca exista cost mai mic.

Da, imi cer scuze, nu am fost atent. In loc de coada, tii heap, dupa drumul minim, si cand vei ajunge prima oara la finish, e clar ca vei ajunge cu costul minim.

E un dijkstra un pic mascat problema asta :).

Asta ziceam si eu :).

@Wef

Merge si dinamica aia de am zis-o mai sus?

La dijkstra trebuie sa stiu matricea costurilor din prima. Ori aici nu stiu costul pentru a ajunge din oricare pozitie in alta alaturata pentru ca nu stiu exact configuratia zarului in acea pozitie.

Nu mi-e clar cum trebuie sa construiesc heapul

Iti tii o structura, sa zicem nod, in felul urmator:


Si heapul il tii min heap, Heap[ x ].Minim fiind din ce in ce mai mic pe masura ce x-ul se apropie de nivelul 1 al heapului. Heap[ 1 ] fiind elementul minim dintre cele din heap, comparate dupa Minim.

Poti citi aici mai multe despre heapuri aici (http://infoarena.ro/heapuri).

De asemenea, poti implementa cu ajutorul structurii de date priority_queue (http://www.cplusplus.com/reference/stl/priority_queue/) din STL (http://www.cplusplus.com/reference/stl/), Despre STL mai poti citi si aici (http://infoarena.ro/stl).

Spor :)

Pe exemplu din problema i-mi poti spune cum arata min heap-ul?

Am gasit blogul http://adcfils.wordpress.com/ si problema e o tema la facultate, deci putem muta threadul in sectiunea teme.