> 话说这题写死我了。。看DISCUSS里也没有类似的算法。。一直怀疑自己算法是不是有错。。
> program pku2329;
> const
>         dx:array[1..4]of longint=(0,1,0,-1);
>         dy:array[1..4]of longint=(1,0,-1,0);
> var
>         map,mark,d,x,y:array[1..400,1..400]of longint;
>         queue:array[0..1000000,1..2]of longint;
>         visited:array[1..400,1..400]of boolean;
>         n,top,bot:longint;
> 
> procedure init;
> var
>         i,j:longint;
> begin
>         readln(n);
>         for i:=1 to n do
>         begin
>                 for j:=1 to n do
>                 begin
>                         read(map[i,j]);
>                         if map[i,j]<>0 then
>                         begin
>                                 inc(bot);
>                                 queue[bot,1]:=i;
>                                 queue[bot,2]:=j;
>                                 mark[i,j]:=map[i,j];
>                                 x[i,j]:=i;
>                                 y[i,j]:=j;
>                                 d[i,j]:=0;
>                                 visited[i,j]:=true;
>                         end;
>                 end;
>                 readln;
>         end;
> end;
> 
> procedure bfs;
> var
>         i:longint;
> begin
>         repeat
>                 inc(top);
>                 for i:=1 to 4 do
>                 if (queue[top,1]+dx[i]>0) and (queue[top,1]+dx[i]<=n)
>                 and (queue[top,2]+dy[i]>0) and (queue[top,2]+dy[i]<=n)
>                 then
>                 begin
>                         if (not visited[queue[top,1]+dx[i],queue[top,2]+dy[i]]) then
>                         begin
>                                 inc(bot);
>                                 queue[bot,1]:=queue[top,1]+dx[i];
>                                 queue[bot,2]:=queue[top,2]+dy[i];
>                                 x[queue[bot,1],queue[bot,2]]:=x[queue[top,1],queue[top,2]];
>                                 y[queue[bot,1],queue[bot,2]]:=y[queue[top,1],queue[top,2]];
>                                 mark[queue[bot,1],queue[bot,2]]:=mark[queue[top,1],queue[top,2]];
>                                 d[queue[bot,1],queue[bot,2]]:=d[queue[top,1],queue[top,2]]+1;
>                                 visited[queue[bot,1],queue[bot,2]]:=true;
>                         end else
>                         if d[queue[top,1],queue[top,2]]+1=d[queue[top,1]+dx[i],queue[top,2]+dy[i]] then
>                         begin
>                                 if (mark[queue[top,1],queue[top,2]]=0) then
>                                         mark[queue[top,1]+dx[i],queue[top,2]+dy[i]]:=0
>                                 else
>                                 if (x[queue[top,1],queue[top,2]]<>x[queue[top,1]+dx[i],queue[top,2]+dy[i]]) or
>                                 (y[queue[top,1],queue[top,2]]<>y[queue[top,1]+dx[i],queue[top,2]+dy[i]])
>                                 then
>                                         mark[queue[top,1]+dx[i],queue[top,2]+dy[i]]:=0;
>                         end;
>                 end;
>         until top=bot;
> end;
> 
> procedure outp;
> var
>         i,j:longint;
> begin
>         for i:=1 to n do
>         begin
>                 for j:=1 to n do
>                 write(mark[i,j],' ');
>                 writeln;
>         end;
> end;
> 
> begin
>         init;
>         if bot>0 then
>         bfs;
>         outp;
> end.

• Re:果断n^2的BFS可以AC啊 90行代码 63MS的 (35) caizhuang0416 2014-02-09 02:07:29