洛谷1443 马的遍历 解题报告

洛谷1443 马的遍历

本题地址： http://www.luogu.org/problem/show?pid=1443

题目描述

有一个n*m的棋盘(1<n,m<=200)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入输出格式

输入格式：

一行四个数据，棋盘的大小和马的坐标

输出格式：

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入输出样例

输入样例#1：

3 3 1 1

输出样例#1：

0    3    2    
3    -1   1    
2    1    4    

题解

广搜BFS

这道题目选择广搜思路会更清晰一些。

我们都知道马的走法（马走日）。

首先，将所有点赋值为-1，如果马没有经过某个点，那么它的值还是保持-1不变。

从起点开始，把当前点移除队列，再从当前点向外扩展一层，将新节点加入队列。同时，用计数器记录步数，赋值给新节点。

当走到终点后，将所有点的值输出即可。

下面附上代码。

代码

const
  dx:array[1..8] of longint=(2,2,-2,-2,1,1,-1,-1);
  dy:array[1..8] of longint=(1,-1,-1,1,2,-2,2,-2);
var
  k,n,m,x,y,i,j,xx,yy,head,tail:longint;
  q:array[1..2000000,1..2] of longint;
  a:array[-2..200,-2..200] of longint;
  dist:array[-10..210,-10..210] of int64;
begin
  read(n,m,x,y);
  fillchar(dist,sizeof(dist),-1);
    q[1,1]:=x; q[1,2]:=y; head:=0; tail:=1; dist[x,y]:=0;
  while head<tail do
    begin
      inc(head);
      x:=q[head,1]; y:=q[head,2];
      for i:=1 to 8 do
        begin
          xx:=x+dx[i]; yy:=y+dy[i];
          if (dist[xx,yy]=-1) and (xx>0) and (xx<=n) and (yy>0) and(yy<=m) then
            begin
              inc(tail);
              q[tail,1]:=xx; q[tail,2]:=yy;
              dist[xx,yy]:=dist[x,y]+1;
            end;
        end;
    end;
  for i:=1 to n do
    begin
    for j:=1 to m do
      begin
        write(dist[i,j]);
        if dist[i,j]=-1 then for k:=1 to 3 do write(' ')
        else if dist[i,j] div 10=0 then for k:=1 to 4 do write(' ')
        else if dist[i,j] div 100=0 then for k:=1 to 3 do write (' ')
        else if dist[i,j] div 1000=0 then for k:=1 to 2 do write(' ')
        else if dist[i,j] div 10000=0 then write(' ');
      end;
      writeln;
    end;
end.

（本文系笔者原创，未经允许不得转载）