Puteti gasi programul pe siteul olimpiadei: oni2010.isjcta.ro

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

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

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.

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

I-mi trebuie  drumul de cost  minim.

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

Poate sa-mi dea cineva probleme care se pot rezolva cu ajutorul metodei divide et impera nerecursiv?