Multumesc mult pentru raspuns...mi-a iesit timpul in 7-8 sec pentru un test de 100x10. O sa mai il cizelez si sper sa imi dea in timp.Inca odata multumesc. Profesorul meu spunea totusi ca exita un algorimt care rezolva liniar....ceva gen 1 ms...aveti vro idee?

Am de rezolvat o problema si nu am nici cea mai mica idee cum sa o rezolv in limitele impuse...adica 3 secunde si maxim 20 de mega de memorie. Va rog daca se poate sa imi spuneti si mie "idee principala". O sa postez aici enuntul problemei. Implementarea pe care am incercato eu presupune impartirea ficarui nod in 4 noduri... problema este ca se ajunge la 40 000 de noduri si avand in vedere ca Dijkstra are O(N^2) timpul de executie a fost mult peste 3 secunde. Va multumesc anticipat!




Se da o tabla asemanatoare cu o tabla de sah, de dimensiune NxN. Pe o casuta de pe tabla se afla un zar; zarul are laturile egale
 ca lungime cu laturile casutei si ocupa perfect suprafata acesteia (adica laturile fetei de jos sunt suprapuse peste laturile casutei).
 Pe fiecare fata a zarului este inscriptionat câte un numar întreg între 1 si 100.

Zarul poate fi deplasat de pe o casuta pe una vecina printr-o rotatie de 90° în jurul uneia dintre laturile casutei ocupate.
Prin deplasari succesive, zarul poate ajunge în orice pozitie de pe tabla. Se defineste costul unui astfel de drum ca suma numerelor aflate pe
 fata de jos a zarului, inclusiv cele pentru prima si ultima casuta din traseu.

Dându-se dimensiunea tablei N, cele sase valori de pe fetele cubului, pozitia initiala a acestuia pe tabla si coordonatele unei
 casute pe care acesta trebuie sa ajunga, se cere sa gaseasca si sa se afiseze un drum de cost minim de la casuta initiala la casuta destinatie.

 

Date de intrare (fisierul cub.in):

N // dimensiunea tablei

fata spate stânga dreapta sus jos // cele 6 valori ale numerelor de pe fete

x1 y1 x2 y2 // coordonatele casutelor sursa, respectiv destinatie, cu numerotare de la 1 la N

 

Datele de iesire (fisierul cub.out):

C // costul drumului

L // lungimea drumului, ca numar de casute (inclusiv cea initiala si cea finala)

x1 y1

x2 y2

.....

xL yL // coordonatele casutelor prin care trece drumul

 

Observatie: initial cubul este asezat cu fata “fata” orientata în directia pozitiva a axei Y, fata “sus” în directia pozitiva a axei
 Z si fata “dreapta” în directia pozitiva a axei X.

Toate coordonatele încep de la 1.

 

Limite:

1 <= N <= 100

 

Exemplu:

INPUT:
8
2 1 1 8 1 1
3 2 4 2


OUTPUT:
6
6
3 2
3 1
2 1
2 2
3 2
4 2