马的遍历

题目描述

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

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 3 3 1 1 输出样例#1： 0 3 2 3 -1 1 2 1 4

思路：

一个比较简单的搜索题，宽搜，计算到达棋盘上各点的步数，更改点的值。

#include<iostream> #include<queue> #include<iomanip> using namespace std; const int maxn=201; int map[maxn][maxn]; int n,m,move[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}}; struct point { int x,y,n; } p; queue<point> q; int main() { int i,j; cin>>n>>m; for(i=0;i<n;i++) for(j=0;j<m;j++) map[i][j]=-1; cin>>p.x>>p.y; p.x--; p.y--; map[p.x][p.y]=0; q.push(p); while(!q.empty()) { point temp; for(i=0;i<8;i++) { temp=q.front(); int x=temp.x+move[i][0]; int y=temp.y+move[i][1]; if(x<0||x>n||y<0||y>m||map[x][y]!=-1) continue; temp.x+=move[i][0]; temp.y+=move[i][1]; temp.n++; q.push(temp); map[temp.x][temp.y]=temp.n; } q.pop(); } for(i=0;i<n;i++) { for(j=0;j<m;j++) cout<<setiosflags(ios::left)<<setw(5)<<map[i][j]; cout<<endl; } return 0; }