话说这题写死我了。。看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.

• 见到pascal的了。。。不得不顶一个 话说楼主你的代码缩进很漂亮啊。。。 (0) xuhaoran510 2010-08-08 09:28:49
• Re:果断n^2的BFS可以AC啊 90行代码 63MS的 (3458) loverszhaokai 2010-08-08 10:08:46
• 楼主没考虑if d[queue[top,1],queue[top,2]]+1<d[queue[top,1]+dx[i],queue[top,2]+dy[i]] 的情况 (50) swust20105592 2011-10-29 10:53:05
  • Re:我是LZ。关于楼上我想解释。 (191) yoyow110w 2012-06-30 01:58:46
• Re:果断n^2的BFS可以AC啊 90行代码 63MS的 (3458) caizhuang0416 2014-02-09 02:05:04
  • Re:果断n^2的BFS可以AC啊 90行代码 63MS的 (35) caizhuang0416 2014-02-09 02:07:29