z-dijamant

Mogu dobiti 2. ili 3. test primjer ovog zadatka?

Moja ideja je da racunam dinamicki:

dp[a][b] = 1+ min{ dp[a-1][b-1], dp[a-1][b], dp[a-1][b+1], dp[a-2][b] }

Jesam nesto propustio?


EDIT: dodano +1

Kao prvo nigdje ne dodajes plus 1 ili nesto. Ti nikako neces povecavati vrijednosti u dp.
I ja sam gledao tocku gore desno, dolje lijevo i dva polja u lijevo.

ja sam na početku na sva polja na kojima je # stavio br 1. i onda išao po matrici i ako imamo polje a,b...tada povećam polje a,b ako sva polja oko njega(gore, dolje, lijevo,desno) imaju broj koji je on imao prije ili veći. daje dobra rješenja ali je presporo..za 3-4 test primjera

[quote author=Frane Kurtovi? link=topic=10395.msg12706#msg12706 date=1206950025]
Kao prvo nigdje ne dodajes plus 1 ili nesto. Ti nikako neces povecavati vrijednosti u dp.
I ja sam gledao tocku gore desno, dolje lijevo i dva polja u lijevo.
[/q]

Da, zaboravio sam dodati +1 u formulu.
Prolazi mi za 12 od 15 test primjera.

Ovo je ključni dio programa:

if( i == 0 || i == 1 || j == 0 || j == M-1 ) dp[i][j] = 1;
else dp[i][j] = min4( dp[i-1][j-1], dp[i-1][j+1], dp[i-2][j], dp[i-1][j] ) + 1;
best = max( best, dp[i][j] );

Ma nema veze, uspio sam riješiti zadatak na drugi način.

Meni bi trebao neki primer posle sedmog(najbolje 8 ili 9 jer su u njima izgleda najmanji ulazni podaci) jer mi 1-7 prolaze, a od 8-20 nijedan. Mislio sam da ce padati na vremenu jer mi je primena ideje delovala presporo ali se ispostavilo da treba max 0.1 sekund, sto mi ne znaci puno jer mi na vise od pola primera daje netacno resenje.

Kontam da ti je negde greska zbog broj polja. Koliko ti je resenje za 999x999 '#' bez ijedne '.'? Koliko obrnuto?

Kao sto sam i predpostavio, opet sam ja napravio neku glupost. Sad radi, ali ipak pada na vremenu na 5 primera. Probacu malo da doteram programcic ali mislim da mi je ideja pogresna(zbog vremena).

Hvala u svakom slucaju.