•adrian.ivanciu
Strain
Karma: -1
Deconectat
Mesaje: 8
|
|
« : 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
|
|
« 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 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
|
|
« 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 @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
|
|
« 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
Mesaje: 8
|
|
« Răspunde #4 : Ianuarie 10, 2009, 21:20:03 » |
|
I-mi trebuie drumul de cost minim.
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« 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
Mesaje: 8
|
|
« 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
|
|
« 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
Mesaje: 8
|
|
« 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
|
|
« 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
|
|
« Răspunde #10 : Ianuarie 11, 2009, 12:57:17 » |
|
E un dijkstra un pic mascat problema asta .
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•toni2007
|
|
« Răspunde #11 : Ianuarie 11, 2009, 13:00:25 » |
|
Asta ziceam si eu . @Wef Merge si dinamica aia de am zis-o mai sus?
|
|
|
Memorat
|
|
|
|
•adrian.ivanciu
Strain
Karma: -1
Deconectat
Mesaje: 8
|
|
« 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
|
|
« Răspunde #13 : Ianuarie 11, 2009, 13:33:29 » |
|
Iti tii o structura, sa zicem nod, in felul urmator: 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
|
|
|
Memorat
|
|
|
|
•adrian.ivanciu
Strain
Karma: -1
Deconectat
Mesaje: 8
|
|
« Răspunde #14 : Ianuarie 11, 2009, 20:23:19 » |
|
Pe exemplu din problema i-mi poti spune cum arata min heap-ul?
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« 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
|
|
|
|
|