题解 P5195 【[USACO05DEC]Knights of Ni 骑士】

· · 题解

这道题目。。。明显的搜索题啊。。。

先算出到灌木丛的距离,再加上到骑士的距离或者是先到灌木丛,然后直接去骑士地方。

就是这么简单。。。

```cpp #include<cstdio> #include<cstring> #include<algorithm> #define N 1001 struct target { int x,y; } t[N*N]; struct queue { int x,y; } q[N*N]; int dicx[4]={0,1,0,-1},dicy[4]={1,0,-1,0}; int n,m,cnt,x1,y1,x2,y2,head,tail,ans=100000000; int a[N][N],dis1[N][N],dis2[N][N]; bool f[N][N]; using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } void bfs1(int x,int y) { head=0; tail=1; f[x][y]=1; q[1].x=x; q[1].y=y; while (head<tail) { head++; int nx=q[head].x,ny=q[head].y; for (int i=0; i<4; i++) { int xx=nx+dicx[i],yy=ny+dicy[i]; if (xx<1||xx>n||yy<1||yy>m)continue; if (f[xx][yy]||a[xx][yy]==1) continue; dis1[xx][yy]=dis1[nx][ny]+1; q[++tail].x=xx; q[tail].y=yy; f[xx][yy]=1; } } } void bfs2(int x,int y) { memset(q,0,sizeof(q)); memset(f,0,sizeof(f)); head=0; tail=1; f[x][y]=1; q[1].x=x; q[1].y=y; while (head<tail) { head++; int nx=q[head].x,ny=q[head].y; for (int i=0; i<4; i++) { int xx=nx+dicx[i],yy=ny+dicy[i]; if (xx<1||xx>n||yy<1||yy>m)continue; if (f[xx][yy]||a[xx][yy]==1) continue; dis2[xx][yy]=dis2[nx][ny]+1; q[++tail].x=xx; q[tail].y=yy; f[xx][yy]=1; } } } int main() { m=read(); n=read(); for (int i=1; i<=n; i++) for(int j=1; j<=m; j++) { a[i][j]=read(); if (a[i][j]==4) { t[++cnt].x=i; t[cnt].y=j; } else if (a[i][j]==2) { x1=i; y1=j; a[i][j]=0; } else if (a[i][j]==3) { x2=i; y2=j; a[i][j]=0; } } bfs1(x1,y1); bfs2(x2,y2); for (int i=1; i<=cnt; i++) { int nx=t[i].x,ny=t[i].y; if (!(dis1[nx][ny]+dis2[nx][ny])) continue; ans=min(ans,dis1[nx][ny]+dis2[nx][ny]); } printf("%d\n",ans); } ``` $\rm Pascal$代码: ```pas const dx:array[1..4]of longint=(-1,1,0,0); dy:array[1..4]of longint=(0,0,-1,1); var n,m,x1,y1,x2,y2,t,i,j,min:longint; a,c,d:array[1..1000,1..1000]of longint; b,e:array[1..1000000,1..2]of longint; f:array[1..1000,1..1000]of boolean; procedure bfs1(x,y:longint); var nx,ny,k,head,tail:longint; begin head:=0; tail:=1; f[x,y]:=true; e[1,1]:=x; e[1,2]:=y; while head<tail do begin head:=head+1; for k:=1 to 4 do begin nx:=e[head,1]+dx[k]; ny:=e[head,2]+dy[k]; if (nx>0)and(nx<=n)and(ny>0)and(ny<=m) then if a[nx,ny]<>1 then if not f[nx,ny] then begin tail:=tail+1; e[tail,1]:=nx; e[tail,2]:=ny; f[nx,ny]:=true; c[nx,ny]:=c[e[head,1],e[head,2]]+1; end; end; end; end; procedure bfs2(x,y:longint); var nx,ny,k,head,tail:longint; begin head:=0; tail:=1; f[x,y]:=true; e[1,1]:=x; e[1,2]:=y; while head<tail do begin head:=head+1; for k:=1 to 4 do begin nx:=e[head,1]+dx[k]; ny:=e[head,2]+dy[k]; if (nx>0)and(nx<=n)and(ny>0)and(ny<=m) then if a[nx,ny]<>1 then if not f[nx,ny] then begin tail:=tail+1; e[tail,1]:=nx; e[tail,2]:=ny; f[nx,ny]:=true; d[nx,ny]:=d[e[head,1],e[head,2]]+1; end; end; end; end; begin readln(m,n); for i:=1 to n do begin for j:=1 to m do begin read(a[i,j]); if a[i,j]=2 then begin x1:=i; y1:=j; a[i,j]:=1; end; if a[i,j]=3 then begin x2:=i; y2:=j; a[i,j]:=1; end; if a[i,j]=4 then begin t:=t+1; b[t,1]:=i; b[t,2]:=j; end; end; readln; end; bfs1(x1,y1); fillchar(f,sizeof(f),false); fillchar(e,sizeof(f),false); bfs2(x2,y2); min:=maxlongint; for i:=1 to t do if (c[b[i,1],b[i,2]]<>0)and(d[b[i,1],b[i,2]]<>0) then if c[b[i,1],b[i,2]]+d[b[i,1],b[i,2]]<min then min:=c[b[i,1],b[i,2]]+d[b[i,1],b[i,2]]; writeln(min); end. ```