某王老师给我们考了一场noip2013的真题。。。心态爆炸！

题目大意：

有一个n*m的棋盘，每个格子上都有一个棋子，有些格子上的棋子能够移动（可移动的棋子是固定的），棋盘中有一个格子是空的，仍何可移动的棋子都能够与空格子交换位置。现在有q个询问，每个询问给出kx,ky,sx,sy,ex,ey，分别为空白格子的坐标，要你移动的棋子，目标位置。对于每个询问，要求你求出，把要求你移动的棋子移到目标位置最少移动几次。

思路分析：

首先讲一下暴力做法吧。

这应该大家都能想得到，BFS嘛，记录要求我们移动的棋子（暂且记作1号格子）当前的位置和空白格子（记作2号格子）的位置，当2移动到1旁边时，那么1就可以与2交换位置。

而正解就是基于暴力展开的。。。

我们发现其实当2移动到1旁边后，便产生了很多无用的状态，我们只需要知道2在1周围的几个状态就够了，因为1格子进行移动时，无非就是和它周围的几个格子交换位置，而交换位置后2仍然在1的周围，所以我们只需要知道2在从1周围的4个格子走到另一个格子的最小花费即可。

我们记一个三元组（x,y,k）其中x，y表示1号棋子的坐标，k表示2号棋子相对1号棋子的位置（0表示在1的上面，1表示在1的右边，2表示在1的左边，3表示在1的下面），当然一心想要偷懒的我粗暴地把三元组压成了一个数，是这么压的(x,y,k)=k*n*m+(x-1)*m+y，嗯，免得你们看不懂代码。。。

那么根据我们先前讲的，设计两种连边：

1、可以在（x，y，0~3）与（x，y，0~3）之间设计一条长度为空白格子从一个位置（x,y的上下左右）走到另一个位置（x,y的上下左右）的最小花费。

2、在（x，y，k）与（x+dx[k]，y+dy[k]，3-k）之间连一条边，其意义便是1号格子与2号格子交换了位置。（现在知道我这么设计方向的(shi)用(wei)心(le)良(tou)苦(lan)了吧）

先把连边预处理出来，然后我们只要第一次计算出初始位置的2号格子移动到1号格子的上下左右的最小花费（可以BFS暴力做）之后，跑一边Dijkstra就完事儿了！

代码实现：

type

  hehe=record

    dist,id:longint;

end;

  haha=record

    x,y,dist:longint;

end;

var

  next,vet,dist:array[1..200000]of longint;

  f:array[1..2000000]of hehe;

  a:array[1..90000]of haha;

  d,fir,visit:array[1..48000]of longint;

  map,vis:array[-50..50,-50..50]of longint;

  dx,dy:array[0..3]of longint;

  sx,sy,ex,ey,kx,ky,xx,yy,n,m,q,i,j,ii,jj,tot,weight,x,y,oo,cost,ans,z,x1,x2,y1,y2:longint;

procedure add(x,y,z:longint);

begin

  inc(tot);

  next[tot]:=fir[x];

  fir[x]:=tot;

  vet[tot]:=y;

  dist[tot]:=z;

end;

function min(x,y:longint):longint;

begin

  if x<y then exit(x) else exit(y);

end;

procedure swap(x,y:longint);

var

  t:hehe;

begin

  t:=f[x]; f[x]:=f[y]; f[y]:=t;

end;

procedure up(x:longint);

begin

  if x=1 then exit;

  if f[x].dist<f[x div 2].dist then begin swap(x,x div 2); up(x div 2); end;

end;

procedure down(x:longint);

var

  k:longint;

begin

  if x*2>n then exit;

  k:=min(f[x*2].dist,f[x*2+1].dist);

  if f[x].dist>k then

    if k=f[x*2].dist then begin swap(x,x*2); down(x*2); end

    else begin swap(x,x*2+1); down(x*2+1); end;

end;

procedure push(x,id:longint);

begin

  inc(weight);

  f[weight].dist:=x;

  f[weight].id:=id;

  up(weight);

end;

procedure pop;

begin

  x:=f[1].id;

  f[1].dist:=f[weight].dist;

  f[1].id:=f[weight].id;

  f[weight].dist:=oo;

  f[weight].id:=oo;

  dec(weight);

  down(1);

end;

procedure dijkstra;

var

  y,i:longint;

begin

  fillchar(visit,sizeof(visit),0);

  while weight>0 do

  begin

    pop;

    if x>4800 then continue;

    if d[x]>=oo then break;

    if visit[x]=1 then continue;

    visit[x]:=1;

    i:=fir[x];

    while i<>0 do

    begin

      y:=vet[i];

      if (dist[i]<oo)and(d[y]>d[x]+dist[i]) then

        begin d[y]:=d[x]+dist[i]; push(d[y],y); end;

      i:=next[i];

    end;

  end;

end;

function bfs(nx,ny,x1,y1,x2,y2:longint):longint;

var

  head,tail,dist,xx,yy,x,y,i:longint;

begin

  if map[x1,y1]+map[x2,y2]<>2 then exit(oo);

  if (x1=x2)and(y1=y2) then exit(0);

  fillchar(vis,sizeof(vis),0);

  head:=0; tail:=1; bfs:=maxlongint;

  a[1].x:=x1; a[1].y:=y1; a[1].dist:=0; vis[x1,y1]:=1;

  while head<>tail do

  begin

    inc(head);

    x:=a[head].x; y:=a[head].y; dist:=a[head].dist;

    for i:=0 to 3 do

    begin

      xx:=x+dx[i]; yy:=y+dy[i];

      if ((xx<>nx)or(yy<>ny))and(map[xx,yy]=1)and(vis[xx,yy]=0) then

      begin

        inc(tail);

        a[tail].x:=xx; a[tail].y:=yy; a[tail].dist:=dist+1;

        vis[xx,yy]:=1;

        if (xx=x2)and(yy=y2) then exit(dist+1);

      end;

    end;

  end;

end;

begin

  read(n,m,q);

  for i:=1 to n do

    for j:=1 to m do

      read(map[i,j]);

  dx[0]:=-1; dy[1]:=1; dy[2]:=-1; dx[3]:=1;

  for i:=1 to n do

    for j:=1 to m do

    if map[i,j]=1 then

      for ii:=0 to 3 do

      begin

        x1:=i+dx[ii]; y1:=j+dy[ii]; x2:=i; y2:=j;

        if map[x1,y1]+map[x2,y2]=2 then

        begin

          add(ii*n*m+(x2-1)*m+y2,(3-ii)*n*m+(x1-1)*m+y1,1);

        end;

        for jj:=0 to 3 do

        begin

          x2:=i+dx[jj]; y2:=j+dy[jj];

          if (ii<>jj)and(map[x1,y1]+map[x2,y2]=2) then

          begin

            cost:=bfs(i,j,x1,y1,x2,y2);

            add(ii*n*m+(i-1)*m+j,jj*n*m+(i-1)*m+j,cost);

          end;

        end;

      end;

  while q>0 do

  begin

    read(kx,ky,sx,sy,ex,ey);

    fillchar(d,sizeof(d),$1f);

    oo:=d[1];

    fillchar(f,sizeof(f),$1f);

    weight:=0;

    if (sx=ex)and(sy=ey) then

    begin

      writeln(0);

      dec(q);

      continue;

    end;

    for i:=0 to 3 do

    begin

      x:=sx+dx[i]; y:=sy+dy[i];

      if map[x,y]=1 then

      begin

        d[i*n*m+(sx-1)*m+sy]:=bfs(sx,sy,kx,ky,x,y);

        push(d[i*n*m+(sx-1)*m+sy],i*n*m+(sx-1)*m+sy);

      end;

    end;

    dijkstra;

    ans:=oo;

    for i:=0 to 3 do

    begin

      z:=i*n*m+(ex-1)*m+ey;

      if d[z]<=ans then ans:=d[z];

    end;

    if ans=oo then writeln(-1) else writeln(ans);

    dec(q);

  end;

end.

巴特西

NOIP提高组2013 D2T3 【华容道】

题目大意：

思路分析：

代码实现：

最新文章

热门文章