[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Лавиринт - помош  XML
Forum Index » Други задачи
Author Message
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

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)?
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
kikoisawsm


[Avatar]

Joined: 02/01/2012 12:20:46
Messages: 9
Offline

Замисли си случај кога точката до која сакаш да стигнеш се наоѓа на координати (5,5). Стигнуваш до точката (4,5) со 1 чекор, па потоа мора да направиш 2 чекори, но неможеш бидејќи сите точки се зафатени. Да стигнеше до точката (4,5) со 3 чекори ќе можеше потоа да направиш 1 чекор за до точката (5,5), но ти веќе си го означил полето за посетено кога си стигнал до него со 1 чекор.
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 чекор.


Поради ова не работи моето решение, објаснето ми е ова во првиот пост
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Епа бараше конкретен пример; тоа ти е конкретниот пример за идејата што ти ја предложив во мојот пост. Дали (4,5,2) е исто што и (4,5,3) или (4,5,1)?
shellcode



Joined: 17/02/2012 00:48:59
Messages: 30
Offline

Фала ви многу, ја решив задачата и конечно ми се разјаснија некои работи. Извинете што вака доцна одговарам
 
Forum Index » Други задачи
Go to:   
Powered by JForum 2.1.8 © JForum Team