菲洛嘉青春动能素135HA FILLMED® NCTF 135HA LED指示灯的常见故障分析 智微智能 Elkhartlake K075终端,零售产业新选择 天空蓝拓客管理系统详细介绍版 muso公链项目 天使计划 是什么?[秘] 独家揭秘最前沿的家装“黑科技”——掌赋 天博体育欧洲杯特辑,东道主法兰西的失意2016 亚马逊的送货侦察员 学习听起来像挡泥板 Google Comics Factory使ML变得容易 笑着说-男性或女性 Amazon Rekognition中更好的人脸检测 关于Spaun的真相-大脑模拟 两个聊天机器人彼此聊天-有趣又怪异 GANPaint:将AI用于艺术 WCF和WF给予社区 从耳朵到脸 所有神经网络的深层缺陷 蠕虫在尾巴上平衡杆子 Kickstarter上的OpenCV AI套件 TensorFlow-Google的开源AI和计算引擎 众包取代新闻工作者 Google的DeepMind学会玩街机游戏 哑机器人V智能机器人 .NET与.NET 5融为一体 Google的深度学习-语音识别 LInQer将.NET LINQ移植到Javascript 机器人TED演讲-新的图灵测试? GAN的发明者加入苹果 您的智能手机会监视您键入的内容 人工智能帮助改善国际象棋 Zalando Flair NLP库已更新 TensorFlow 1.5包含移动版本 AlphaGo输了一场比赛-比分3-1 虚拟机器学习峰会 Microsoft开源AI调试工具 SharePoint走向移动 F#4.0发出文化变革的信号 克里斯蒂拍卖AI艺术品 人工智能如何区分 Facebook在蒙特利尔的新AI实验室 Mozilla想要您的声音 微软使用极深的神经网络赢得ImageNet 建立AI合作伙伴关系 .NET Core 3-Microsoft几乎回到了起点 神经网络-更好的销售商? Google使用AI查找您的住所 虹膜-适用于Android的Siri证明苹果没有优势 TensorFlow 2提供更快的模型训练 深度学习研究人员将为Google工作
您的位置:首页 >运维 >

P1443 马的遍历【BFS】

https://www.luogu.com.cn/problem/P1443

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0323-1 1214

题解:一般情况下的BFS,每个能走的方向都保存下来,更新需要输出的地图。BFS的写法就是一般的写法,注意的是输出时需要宽5格。一开始用了cin,不太熟练使用格式化输出,就改成了scanf/printf输入输出了。

#include <stdio.h>#include <string.h>#include<bits/stdc++.h>using namespace std;typedef long long ll;int mp[410][410];int vis[410][410];struct node{int x,y,step;} w,l;int dx[] = {-1,-1,-2,-2,1,1,2,2};int dy[] = {-2,2,-1,1,-2,2,1,-1};void bfs(int sx, int sy,int n, int m){memset(vis,0,sizeof(vis));memset(mp,-1,sizeof(mp));queue<node>q;w.x = sx;w.y = sy;w.step = 0;q.push(w);vis[w.x][w.y] = 1;mp[sx][sy] = 0;while(!q.empty()){w = q.front();q.pop();for(int i = 0; i < 8; i ++){int tx = dx[i] + w.x;int ty = dy[i] + w.y;if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[tx][ty] == 0){l.x = tx;l.y = ty;l.step = w.step+1;q.push(l);vis[tx][ty] = 1;mp[tx][ty] = l.step;}}}}int main(){int n,m,sx,sy;//cin >> n >> m >> sx >> sy;scanf("%d %d %d %d", &n,&m,&sx,&sy);bfs(sx,sy,n,m);for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){//if(j == 1)//cout << mp[i][j];//else//cout << "" << mp[i][j] ;printf("%-5d",mp[i][j]);}printf("\n");}return 0;}

 

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。