题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入格式
一行四个数据，棋盘的大小和马的坐标
输出格式
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
输入输出样例
输入: 输出： 3 3 1 1 0 3 2 3 -1 1 2 1 4
下面正式进入题解内容
这道题目我用的是广度优先搜索（BFS）
首先要输入马的位置（当我没说）
然后就是要考虑马的八个方向；
int dx[10]={1,2,2,1,-1,-2,-2,-1}; int dy[10]={2,1,-1,-2,-2,-1,1,2};
我们都知道，广度优先搜索利用的是队列，所以我们先建立队列：
qx[]表示队列，head表示队列头，tail表示队列尾。
下面开始正常操作：
1.将元素放入队列尾；
2.循环：当队列头不等于队列尾时循环。
3.取出队列头。
4.按八个方向从马的坐标向外延伸。
5.将可以最先落脚的地方标记，并记录步数。
6.将这个点放入队列头。
好了，就这么简单。
下面是BFS部分的代码：（未经修改，放心食用）
1 void bfs(int x,int y) 2 { 3 head=0;tail=0; 4 qx[++tail]=x,qy[tail]=y; 5 ans[x][y]=0; 6 used[x][y]=1; 7 while(head!=tail) 8 { 9 int x=qx[++head],y=qy[head]; 10 for(int i=0;i<8;i++) 11 { 12 int nx=x+dx[i],ny=y+dy[i]; 13 if(nx>=1&&nx<=n&&ny>=1&&ny<=m) 14 { 15 if(used[nx][ny]==0) 16 { 17 used[nx][ny]=1; 18 ans[nx][ny]=ans[x][y]+1; 19 qx[++tail]=nx,qy[tail]=ny; 20 } 21 } 22 } 23 } 24 }
输入输出问题就不必说了。
但要注意题目要求输出左对齐，宽5格（不能用空格！）
题目完整代码如下：（经过部分修改，禁止复制粘贴）
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 int dx[10]={1,2,2,1,-1,-2,-2,-1}; 7 int dy[10]={2,1,-1,-2,-2,-1,1,2}; 8 int head,tail,ans[500][500],qx[16000000001],qy[16000000001],n,m,nx,ny; 9 bool used[1000][1000]; 10 void dfs(int x,int y) 11 { 12 head=0 tail=0; 13 qx[++tail]=x,qy[tail]=y; 14 ans[x][y]=0; 15 used[x][y]=1; 16 while(head!=tail) 17 { 18 int x=qx[++head],y=qy[head]； 19 for(int i=0;i<8;i++) 20 { 21 int nx=x+dx[i],ny=y+dy[i]； 22 if(nx>=1&&nx<=n&&ny>=1&&ny<=m) 23 { 24 if(used[nx][ny]==0) 25 { 26 used[nx][ny]=1；27 ans[nx][ny]=ans[x][y]+1；28 qx[++tail]=nx,qy[tail]=ny； 29 } 30 } 31 } 32 } 33 } 34 int main() 35 { 36 int x,y; 37 cin>>n>>m; 38 for(int i=0;i<n;i++) 39 { 40 for(int j=1;j<=m;j++) 41 { 42 ans[i][j]=-1; 43 } 44 } 45 cin>>x>>y; 46 bfs(x,y); 47 for(int i=1;i<=n;i++) 48 { 49 for(int j=1;j<=m;j++) 50 printf("%d",ans[i][j]); 51 cout<<endl; 52 } 53 return 0;//不写return 0，考试就爆零 54 }
最后本蒟蒻祝福大家：
.JPG)
