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 ....

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

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

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

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);

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 ?