Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:果断n^2的BFS可以AC啊 90行代码 63MS的In Reply To:果断n^2的BFS可以AC啊 90行代码 63MS的 Posted by:yoyow110w at 2010-07-25 21:02:14 > 话说这题写死我了。。看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. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator