Author |
Message |
04/05/2013 17:03:40
|
shellcode
Joined: 17/02/2012 00:48:59
Messages: 30
Offline
|
Здраво. Имам проблем со задачава. Составив решение кое на крајот излезе дека не гарантира точност. Идејата ми беше следнава: Почнувам од "P" и се движам едно поле горе, долу, лево и десно. Тој пат до тоа поле го запишувам во матрица. Потоа се движам од тоа поле до наредните со два чекори горе, долу, лево и десно, после со три чекори исто итн. Ако сретнам некое поле каде што неговата вредност во матрицата( т.е патот да се стигне до тука ) е поголема од таа што ја добивам нова ја запишувам новата. Е сега има случај каде што мојот код вели дека до К нема пат, на пример:
Овде мојот код вели дека нема пат до К, а пат има и е 3. ( Горе за еден, долу два и десно три).
Според моето решение прво се запишува еден во матрицата горе, долу, лево и десно, и кога пробува да оди надолу за 2 гледа дека патот 2 е поголем од 1 што е запишан во полето и завршува.
Еве го кодот:
Друго решение што ми текнува е да почниме од К. На пример ја имаме следната матрица:
До К може да се стигне со еден чекор од полето (1,1) и со два чекори од полето (1,0). Ако пробаме да стигнеме од (1,1) со еден чекор значи до него сме стигнале со три чекори. Гледаме дека до него неможе да се стигне со три чекори така што тој испаѓа од игра. Пробуваме од (1,0). Ако до К стигнеме од (1,0) со два чекори, тогаш до него сме стигнале со еден чекор. Гледаме дека со еден чекор може да се стигне од P и имаме решение. Проблемот во ова е што незнам како да го напишам
Ако може некоја идеја да ми дадете или било каква помош би ви бил благодарен. Поздрав
This message was edited 1 time. Last update was at 04/05/2013 17:05:10
|
|
|
05/05/2013 00:01:01
|
obi1kenobi
Joined: 18/02/2010 20:01:33
Messages: 168
Offline
|
Проблемот што го идентификуваше во првата идеја е вистински, значи на добар пат си.
Втората идеја што ја имаше е доста комплицирана, и колку што ми текнува мене не може ефикасно да се напише (барем не со разумен број на линии код).
Значи назад на првата идеја. Бфс функционира на тој начин што те спречува да посетуваш состојби кои се еквивалентни -- значи ако имаме две еквивалентни состојби, множествата состојби во кои може да се премине од нив мора да се еднакви.
Нека (x,y,k) означува дека си во поле (x,y) и следниот потег е k чекори долг. Прашањето е, дали (x,y,1) е еквивалентна состојба со (x,y,2) и (x,y,3)?
|
|
|
05/05/2013 08:03:43
|
shellcode
Joined: 17/02/2012 00:48:59
Messages: 30
Offline
|
Ne ti ja razbiram bas idejata. Ako moze da mi objasnis na konkreten primer bi bilo super. Izvini za latinica od tel sum :p
|
|
|
06/05/2013 00:12:23
|
kikoisawsm
Joined: 02/01/2012 12:20:46
Messages: 9
Offline
|
Замисли си случај кога точката до која сакаш да стигнеш се наоѓа на координати (5,5). Стигнуваш до точката (4,5) со 1 чекор, па потоа мора да направиш 2 чекори, но неможеш бидејќи сите точки се зафатени. Да стигнеше до точката (4,5) со 3 чекори ќе можеше потоа да направиш 1 чекор за до точката (5,5), но ти веќе си го означил полето за посетено кога си стигнал до него со 1 чекор.
|
|
|
06/05/2013 16:36:23
|
shellcode
Joined: 17/02/2012 00:48:59
Messages: 30
Offline
|
kikoisawsm wrote:Замисли си случај кога точката до која сакаш да стигнеш се наоѓа на координати (5,5). Стигнуваш до точката (4,5) со 1 чекор, па потоа мора да направиш 2 чекори, но неможеш бидејќи сите точки се зафатени. Да стигнеше до точката (4,5) со 3 чекори ќе можеше потоа да направиш 1 чекор за до точката (5,5), но ти веќе си го означил полето за посетено кога си стигнал до него со 1 чекор.
Поради ова не работи моето решение, објаснето ми е ова во првиот пост
|
|
|
06/05/2013 20:59:25
|
obi1kenobi
Joined: 18/02/2010 20:01:33
Messages: 168
Offline
|
Епа бараше конкретен пример; тоа ти е конкретниот пример за идејата што ти ја предложив во мојот пост. Дали (4,5,2) е исто што и (4,5,3) или (4,5,1)?
|
|
|
04/07/2013 16:39:02
|
shellcode
Joined: 17/02/2012 00:48:59
Messages: 30
Offline
|
Фала ви многу, ја решив задачата и конечно ми се разјаснија некои работи. Извинете што вака доцна одговарам
|
|
|
|
|
|