Easy ?

Posted by

ZamNick 17 Jan 2014 22:26

When I've written bfs I've got TL29, when I've written Kd-tree, I've got TL26 ....

Hey, guys, give me some hints how to solve this problem, please ....

Re: Easy ?

Posted by

shad 17 Jan 2014 22:58

DP. I select min answers from nearest cells to depth <= 3 (i.e. manhatten distance), calculated left-down to up-right.

Re: Easy ?

Posted by

shad 17 Jan 2014 23:11

Sorry for my wrong Englisish - answer from nearesr cels calculated from left-down to up-right and wise versa.

Re: Easy ?

Posted by

ZamNick 18 Jan 2014 02:12

Ha-ha ..... my DP give me WA5 :)

Can you explain me how to build DP in this problem, what the base of DP and so on ???

Re: Easy ?

Posted by

shad 18 Jan 2014 10:47

In direction :

for(j=2; j<m1; j++){

for(i=2; i<n1; i++){

look best from cells in quadrant :

int n2 = i-3, m2 = j-3;

for(int i1=i; i1>n2; --i1){

for(int j1=j; j1>m2; --j1){

...

b[i][j] = best;

and repeat 4 times for all 4 directins and corresponding quadrant.

print answer :

for(i=2; i<n1; i++){

int sh=0;

for(j=2; j<m1; j++){

P p=P(i,j);

int d = p.dist(b[i][j]);

sh += sprintf(ans+sh,"%d ", d);

// printf("%d ", d);

}

puts(ans);

Re: Easy ?

Posted by

ZamNick 18 Jan 2014 15:30

And finally, I've got AC .... Thanks for your help, guy, you've taught me cool trick .... But, nevertheless, can you explain, why it is work, when we look in 4 direction, maybe 3 is enough (but it's not enough, 'cause I've got WA :) ) ? Do you have mathematical evidence ?