【Usaco 2007 Dec silver】穿越泥地 (Standard IO)

    xiaoxiao2021-03-26  13

    题意:

    FJ的屋子在平面坐标(0, 0)的位置,贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。当然咯,FJ也看到了地上的所有N(1 <= N <= 10,000)个泥塘,第i个泥塘的坐标为(A_i, B_i) (-500 <= A_i <= 500;-500 <= B_i <= 500)。每个泥塘都只占据了它所在的那个格子。不能走到池塘,而且只能平行x,y轴走。

    思路:

    bfs,加上记忆化

    程序:

    type Point=record x,y,w:longint; end; const maxn=500; dx:array [1..4] of longint=(1,-1,0,0); dy:array [1..4] of longint=(0,0,1,-1); var a:array [-maxn-2..maxn+1,-maxn-2..maxn+2] of boolean; x,y,x1,y1,n,i,j:longint; state:array [1..1000000] of Point; function cheak(x,y:longint):boolean; begin if a[x,y] then exit(false); if (x<-500) or (x>500) or (y<-500) or (y>500) then exit(false); exit(true); end; procedure bfs; var y1,x1,i,j,head,tail:longint; begin head:=0; tail:=1; state[1].x:=0; state[1].y:=0; state[1].w:=0; repeat inc(head); for i:=1 to 4 do begin x1:=state[head].x+dx[i]; y1:=state[head].y+dy[i]; if cheak(x1,y1) then begin inc(tail); a[x1,y1]:=true; state[tail].x:=x1; state[tail].y:=y1; state[tail].w:=state[head].w+1; end; if (x1=x) and (y1=y) then begin writeln(state[tail].w); halt; end; end; until head=tail; end; begin readln(x,y,n); for i:=1 to n do begin readln(x1,y1); a[x1,y1]:=true; end; bfs; writeln(-1); end.
    转载请注明原文地址: https://ju.6miu.com/read-600278.html

    最新回复(0)