Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: cube  (Citit de 5917 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
adrian.ivanciu
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« : Ianuarie 09, 2009, 15:54:30 »

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
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #1 : Ianuarie 09, 2009, 18:40:17 »

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 Smile
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?
« Ultima modificare: Ianuarie 09, 2009, 20:04:22 de către alexandru » Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #2 : Ianuarie 09, 2009, 22:36:04 »

@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 Smile

@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.
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #3 : Ianuarie 10, 2009, 12:24:45 »

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


Karma: -1
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #4 : Ianuarie 10, 2009, 21:20:03 »

I-mi trebuie  drumul de cost  minim.
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #5 : Ianuarie 10, 2009, 21:58:34 »

@alexandru

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


Karma: -1
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #6 : Ianuarie 10, 2009, 22:40:27 »

A reusit sa rezolve cineva problema? Daca da il rog sa-mi spuna si mie cum.
Multumesc anticipat!
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #7 : Ianuarie 10, 2009, 23:28:32 »

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


Karma: -1
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #8 : Ianuarie 11, 2009, 10:15:21 »

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.
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #9 : Ianuarie 11, 2009, 12:41:13 »

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.
« Ultima modificare: Ianuarie 11, 2009, 12:46:51 de către Pripoae Teodor Anton » Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #10 : Ianuarie 11, 2009, 12:57:17 »

E un dijkstra un pic mascat problema asta Smile.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #11 : Ianuarie 11, 2009, 13:00:25 »

Asta ziceam si eu Smile.

@Wef

Merge si dinamica aia de am zis-o mai sus?
Memorat
adrian.ivanciu
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #12 : Ianuarie 11, 2009, 13:13:09 »

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
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #13 : Ianuarie 11, 2009, 13:33:29 »

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

Cod:
struct nod{
    int Minim, CoordX, CoordY, FatzaZar.
};

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.

De asemenea, poti implementa cu ajutorul structurii de date priority_queue din STL, Despre STL mai poti citi si aici.

Spor Smile
Memorat
adrian.ivanciu
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #14 : Ianuarie 11, 2009, 20:23:19 »

Pe exemplu din problema i-mi poti spune cum arata min heap-ul?
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #15 : Ianuarie 13, 2009, 06:06:55 »

Am gasit blogul http://adcfils.wordpress.com/ si problema e o tema la facultate, deci putem muta threadul in sectiunea teme.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines