首页 > 其他 > 详细

洛谷 P1443 马的遍历

时间:2019-02-07 22:28:24      阅读:254      评论:0      收藏:0      [点我收藏+]

题目描述

有一个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   

解题思路:
本题数据较水,直接暴力bfs就AC了,先将全图答案初始化为-1,从起点开始,将起点入队列并更新答案为0.每次弹出队首元素,枚举队首元素可以走到的八个点,如果没有超出边界并且还没有得到最优解,就更新它的答案并将它入队列,循环下去,直到队列为空,输出答案即可.

AC代码:
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,x,y,ans,a[405][405]; 
 4 int mx[8] = {2,-2,2,-2,-1,1,-1,1},my[8] = {1,1,-1,-1,2,2,-2,-2};//八个方向 
 5 bool vis[405][405];//储存每个点是否已经为最优答案 
 6 queue<int > q,q1;//q储存入队点行号,q1储存入队点列号 
 7 int main()
 8 {
 9     cin >> n >> m >> x >> y;
10     memset(a,-1,sizeof(a));//将全图初始化为-1 
11     q.push(x);
12     q1.push(y);//起点入队 
13     a[x][y] = 0;//更新起点答案 
14     vis[x][y] = 1;//标记 
15     while(!q.empty()) {
16         int u = q.front();//弹出队首元素 
17         int v = q1.front();//弹出队首元素 
18         q.pop();q1.pop();
19         for(int i = 0; i <= 7; i++) {//枚举八个点 
20             int x1 = mx[i] + u; int y1 = my[i] + v;
21             if(x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && !vis[x1][y1]) {//解题思路过程 
22                 a[x1][y1] = a[u][v] + 1;
23                 vis[x1][y1] = 1;
24                 q.push(x1);q1.push(y1);
25             }
26         }
27     }
28     for(int i=1;i<=n;i++)
29     {
30         for(int j=1;j<=m;j++)
31         cout<<left<<setw(5)<<a[i][j];//题目要求左对齐,宽5格 
32         cout<<endl;
33     }
34 return 0;
35 }

 




洛谷 P1443 马的遍历

原文:https://www.cnblogs.com/lipeiyi520/p/10355623.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!