You don't need to sum the branches, you need to do binary OR "|" on them.

Таким образом, если для данного перекрёстка нет подразделений СКБ Контур находящихся ближе, чем в 6 кварталах, то мы обозначим его числом 0.
Carefully read this part of text.

Who know O(H*W) or, O(H*W*5) algo ???

Each crossroads in the input is the binary OR of its branches, so a 5 (binary 101) at some crossroads in the input means there are branches 4 (100) and 1 (001) there.

As for the output, for each crossroads where there are no branches (each 0, let's call this crossroads P), repeat this:
Find the Manhattan (vertical+horizontal) distance to the closest branch from C. In the description, this closest distance is 2. Next, find all branches that lie on this exact distance from C. In the description, these are branches with number 16, 8, and 4. The output at location P should reflect all types of branches at distance 2 by ORing these numbers together, and in the description we get 28 (binary 10000 | 1000 | 100).

 Please explain the test, I think there 're something wrong or I
don't understand the task.

Does anybody know anything special about 17th test? I've wrote a program, and it works on sample (I use OR, of course), and on all my tests, but...

15 19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1671 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1091 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1942 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 822 0 0 0 0 0 0 0 0 1197
0 0 0 0 870 0 0 0 1719 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 640 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1871 0 0 0
0 57 0 0 0 0 0 0 0 0 0 500 0 0 0 0 0 0 0
0 0 0 0 0 1743 0 557 0 0 0 0 0 0 0 0 0 0 0
0 1153 0 0 0 0 768 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1364 0 0 0 0 0 0 1094 0 0 0 0 0 0 0
0 0 724 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 212 0 0 0 0 0 0 20 0

I seriously think that sample output is screwed up. For example, the lowest line reads:

-1 1 4 - 1 4

But taking into account the proximity of the branch with ID=4
(bin: 100) and the branch with ID=1 (bin: 001) shouldn't all non-negative numbers in line equal 5( bin: 101), like

-1 5 5 -1 5 ?

Could someone make it clear for me? I would be very grateful;-)

#include<iostream>
using namespace std;

struct point{
    int x,y,kol;
};

int a[152][152]={{0}},val[152][152]={{0}};
int m,n;

void query(int i1,int j1,int step=5)
{
    int i,j,pr[152][152]={{0}},n1;
    int x1,y1;
    int x[5]={0,-1,0,1,0},y[5]={0,0,1,0,-1};
    point q[1000]={0},k;

    i=n1=1;
    q[1].x=i1;q[1].y=j1;
    while(i<=n1)
    {
        k=q[i];
        for(j=1;j<=4;j++)
        {
            x1=k.x+x[j];y1=k.y+y[j];
            if(pr[x1][y1]==0 && k.kol<step && (x1>=1 && x1<=n && y1>=1 && y1<=m))
            {
                if(a[x1][y1]!=0){val[i1][j1]|=a[x1][y1];if(k.kol<step)step=k.kol+1;}
                n1++;
                q[n1].x=x1;
                q[n1].y=y1;
                q[n1].kol=k.kol+1;
                pr[x1][y1]=1;
            };
        }
        i++;
    }


}
int main()
{
    int i,j,k;

    cin>>n>>m;

    for(i=1;i<=n;i++)for(j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]!=0)val[i][j]=-1;}

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                query(i,j,5);
            }
        }

    for(i=1;i<=n;i++)
    {
        cout<<endl;
        for(j=1;j<=m;j++)cout<<val[i][j]<<" ";
    }

    return 0;
}

I got TL on #13 :(. Does any body konw the test? I use BFS.

    To get AC you should not make the sum of all the types of nearest brangches but the "or" in pascal and "|" in c++. examle:
1+5+2=8 but you get WA
1|5|2=7 in c++ to get AC
1 or 5 or 2 =7 in pascal to get AC
    I don't know why, but this is the way to get accepted. Can anyone explain why? (the problem text seems ambiguos to me).

I got WA on test17. I can't find my mistakes....
I think the sample test is incorrect.
My solution got the answer is :
2 2 -1 2 -1
3 2 2 7 2
1 8 7 5 7
1 6 5 -1 5
-1 1 4 -1 4
But the sample output is :
2 2 -1 2 -1
3 2 2 7 2
1 7 7 5 7
1 5 5 -1 5
-1 1 4 -1 4
I think the sample output is wrong , isn't it ???
Is my answer right ?
Who can tell me ????

This is my code :
const
  Maxn = 200 ;
var
  h : Array [0..Maxn,0..Maxn] Of LongInt ;
  cost : Array [0..Maxn,0..Maxn] Of Int64 ;
  t : Array [0..6*Maxn] Of LongInt ;
  n , m , i , j , k , len : Integer ;

  Function  check ( k : LongInt ) : Boolean ;
    var
      i : Integer ;
    begin
     check := false ;
     if k = 0 then exit ;
     for i := 1 to len do
      if k = t[i] then exit ;
     check := true ;
    end;

  procedure goin  ( x , y , xi , yi : Integer ) ;
    begin
     if check ( h[xi,yi] ) then
      begin
       Inc ( cost[x,y] , h[xi,yi] ) ;
       Inc ( len ) ;
       t[len] := h[xi,yi] ;
      end;
    end;

  procedure Bfs ( x , y , k : Integer ) ;
    var
      i , j , xi , yi : Integer ;
    begin
     len := 0 ;
     for i := 1 to k - 1 do
      begin
       xi := x + i ;
       if xi > n then break ;
       if y + k - i <= m then goin ( x , y , xi , y + k - i ) ;
       if y - k + i >  0 then goin ( x , y , xi , y - k + i ) ;
      end;

     for i := 1 to k - 1 do
      begin
       xi := x - i ;
       if xi < 0 then break ;
       if y + k - i <= m then goin ( x , y , xi , y + k - i ) ;
       if y - k + i >  0 then goin ( x , y , xi , y - k + i ) ;
      end;

     if y + k <= m then goin ( x , y , x , y + k ) ;
     if y - k >  0 then goin ( x , y , x , y - k ) ;
     if x + k <= n then goin ( x , y , x + k , y ) ;
     if x - k >  0 then goin ( x , y , x - k , y ) ;
    end;

begin
 read ( n , m ) ;
 for i := 1 to n do
  for j := 1 to m do
   read ( h[i,j] ) ;

 for i := 1 to n do
  for j := 1 to m do
   if h[i,j] = 0
    then begin
          for k := 1 to 5 do
           begin
            Bfs ( i , j , k ) ;
            if len > 0 then break ;
           end;
         end
    else cost[i,j] := -1 ;

 for i := 1 to n do
  begin
   write ( cost[i,1] ) ;
   for j := 2 to m do
    write ( ' ' , cost[i,j] ) ;
   writeln ;
  end;
end.

when you are caculating,don't use +,use or!

I don't understand why the Answer is that
in the input of the problem
specialy the one [1,1]=2

{*2*} 2 -1 2 -1
3 2 2 7 2
1 7 7 5 7
1 5 5 -1 5
-1 1 4 -1 4

if you know the answer please help me.
with best wishes
pooya

The confusion about the test example lies in the fact that
if you carefully read the problem (after you tried to send a solution
that got a WA :)  you see that you need to sum up not all the values
(a sum of branch types in the cell) in the given distance, but only
values for different branch types.

Although, I agree that the problem is not described very well.

why don't output in 3rd row , 2nd colum be 8 , fomr 1 + 5 + 2
explain me about this problem please.

Sample Input
5 5
0 0 2 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 5 0
1 0 0 4 0
Sample Output
2 2 -1 2 -1
3 2 2 7 2
1 7 7 5 7
1 5 5 -1 5
-1 1 4 -1 4

const MAXN=15;
type
   data=array[1..4] of 0..1;
var
  d:array[1..MAXN,1..MAXN] of data;
  p:array[1..MAXN,1..MAXN] of 0..1;
  a:array[1..MAXN,1..MAXN] of integer;
  h,w,i,j,k,t,s,pi,pj:integer;
  mmm:data;

function exto(a:data):integer;
var i,s,t:integer;
begin
  s:=0; t:=1;
  for i:=1 to 4 do
  begin
    s:=s+t*a[i];
    t:=t*2;
  end;
  exto:=s;
end;

function equal(a,b:data):boolean;
var i:integer;
begin
  equal:=false;
  for i:=1 to 4 do
    if a[i]<>b[i] then exit;
  equal:=true;
end;

function ok(i,j:integer):boolean;
begin
  if (i<1) or (j<1) or (i>h) or (j>w) then ok:=false else
ok:=true;
end;

procedure add(var a:data; b:data);
var i:integer;
begin
   for i:=1 to 4 do
     if b[i]=1 then a[i]:=1;
end;

begin
  assign(input,'1121.in');
  reset(input);
  read(h,w);
  for i:=1 to h do
  for j:=1 to w do
  begin
    read(s);
    if s<>0 then p[i,j]:=1;
    t:=8;
    for k:=4 downto 1 do
    begin
      if s-t>=0 then begin dec(s,t); d[i,j,k]:=1; end;
      t:=t div 2;
    end;
    writeln(s);
  end;

  for i:=1 to h do
  begin

    for j:=1 to w do
    begin

      a[i,j]:=-1;

      if p[i,j]=0 then
      begin
        for k:=1 to 5 do
        begin
          mmm:=d[i,j];
          for pi:=-k to k do
          begin
            pj:=k-abs(pi);
            if (ok(i+pi,j+pj)) then add(mmm,d[i+pi,j+pj]);
            pj:=-pj;
            if (pj<>0) and (ok(i+pi,j+pj)) then add(mmm,d
[i+pi,j+pj]);
          end;
          if not equal(d[i,j],mmm) then break;
        end;
        a[i,j]:=exto(mmm);
      end;

      write(a[i,j]:2,' ');

    end;
    writeln;

  end;

end.

const MAXN = 150;
type  pointtype = record
                    x,y:byte;
                  end;
var a,b:array[1..MAXN,1..MAXN]of integer;
    c:array[1..MAXN,1..MAXN]of byte;
    s1,s2:array[1..10000]of pointtype;
    N,M,h1,h2,tek,i,j:integer;
procedure rec(x,y,k:byte);
begin
  if (x=0)or(y = 0)or(x = N+1)or(Y = M+1) then exit;
  if (a[x,y] = 0)and((c[x,y] = 0)or(c[x,y] = tek)) then
  begin
    b[x,y]:=b[x,y] or k;
    if c[x,y] = 0 then
    begin
      c[x,y]:=tek;
      inc(h2);
      s2[h2].x:=x;s2[h2].y:=y;
    end;
  end;
end;

begin
{ assign(input,'1121.dat');reset(input);}
  readln(N,M);
  for i:=1 to N do for j:=1 to M do read(a[i,j]);
  for i:=1 to N do for j:=1 to M do if a[i,j]<>0 then
  begin
     inc(h1);
     s1[h1].x:=i;s1[h1].y:=j;{s1[h1].k:=a[i,j];}
     b[i,j]:=a[i,j];
  end;
  tek:=0;
  while true do
  begin
     inc(tek);if tek = 6 then break;
     if h1 = 0 then break;
     h2:=0;
     for i:=1 to h1 do
     begin
       rec(s1[i].x+1,s1[i].y,b[s1[i].x,s1[i].y]);
       rec(s1[i].x-1,s1[i].y,b[s1[i].x,s1[i].y]);
       rec(s1[i].x,s1[i].y-1,b[s1[i].x,s1[i].y]);
       rec(s1[i].x,s1[i].y+1,b[s1[i].x,s1[i].y]);
     end;
     h1:=h2;
     for i:=1 to h1 do s1[i]:=s2[i];
  end;
  for i:=1 to N do
  begin
    for j:=1 to M-1 do
    begin
      if a[i,j] = 0 then write(b[i,j],' ')
      else write(-1,' ');
    end;
    if a[i,M] = 0 then writeln(b[i,M])
    else writeln(-1);
  end;
end.

I don't understand why answer for
5 5
0 0 2 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 5 0
1 0 0 4 0

must be
2 2 -1 2 -1
3 2 2 7 2
1 7 7 5 7
1 5 5 -1 5
-1 1 4 -1 4

i think that b[4, 2] must be 6 and b[3, 2] must be 8

Vokin Andrei e-mail: vok@sbor.ru