洛谷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.  

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

转载于:https://www.cnblogs.com/yzm10/p/4751989.html