当前位置: 首页 > news >正文

马的移动

小明很喜欢下国际象棋,一天,他拿着国际象棋中的“马”时突然想到一个问题:
给定两个棋盘上的方格a和b,马从a跳到b最少需要多少步?
现请你编程解决这个问题。

输入格式:

输入包含多组测试数据。每组输入由两个方格组成,每个方格包含一个小写字母(a~h),表示棋盘的列号,和一个整数(1~8),表示棋盘的行号。

输出格式:

对于每组输入,输出一行“To get from xx to yy takes n knight moves.”。

限制:

空间限制:32MByte
时间限制:1秒

样例:

输入:e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
输出:To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

提示:

提示:国际象棋棋盘为8格*8格,马的走子规则为,每步棋先横走或直走一格,然后再往外斜走一格。

二话不说,上代码:

#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
struct node {int x,y,step;
};
int vis[8][8];
int sx,sy,ex,ey,ans;
int to[8][2]= {-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};
int check(int x,int y) {if(x<0 || y<0 || x>=8 || y>=8)return 1;if(vis[x][y])return 1;return 0;
}
void bfs() {int i;queue<node> Q;node a,next;a.x = sx;a.y = sy;a.step = 0;vis[sx][sy] = 1;Q.push(a);while(!Q.empty()) {a = Q.front();Q.pop();if(a.x == ex && a.y == ey) {ans = a.step;return ;}for(i=0; i<8; i++) {next = a;next.x+=to[i][0];next.y+=to[i][1];if(check(next.x,next.y))continue;next.step = a.step+1;vis[next.x][next.y] = 1;Q.push(next);}}return ;
}int main() {char ch1[10],ch2[10];while(~scanf("%s%s",ch1,ch2)) {sx = ch1[0]-'a';sy = ch1[1]-'1';ex = ch2[0]-'a';ey = ch2[1]-'1';memset(vis,0,sizeof(vis));bfs();printf("To get from %s to %s takes %d knight moves.\n",ch1,ch2,ans);}return 0;
}

相关文章:

  • 递归函数(详解)
  • 函数的定义与变量作用域
  • 一维数组详解
  • continue和break详解
  • while循环 dowhile循环 for循环(C++)
  • 选择语句详解(C++)
  • 赋值语句、变量、数学表达式、位运算详解(C++)
  • 标准输入输出详解(C++)
  • 变量、变量类型与cin的基本用法详解(C++)
  • 程序设计与编译(C++入门)
  • 冒泡排序详解(C++)
  • 线段树-懒标记实现
  • 树的最大独立集详解(C++)
  • 快速排序C++方法(3种)
  • 树的重心详解(C++)
  • 树的最长路径详解(C++)
  • 格雷码的生成详解(C++)(附格雷码对照表)
  • 五子棋小游戏(C++)
  • 其他进制转化为十进制 详解
  • 进制转换的方法 详解
  • 哈夫曼树的生成详解(C++)
  • 同余方程(Day 2)
  • 小 C 的数(number)(C++)
  • 求三角形面积(C++)
  • 温度转换(C++)
  • map 详解(C++)
  • 素MM 详解(C++)
  • 仙岛求药 详解(C++)
  • dijkstra + 优先队列(C++)
  • 深度优先搜索 详解(C++)
  • 贪心算法详解(C++)
  • 对称二叉树 详解(C++)
  • 小 C 的数学(math)详解
  • C++小游戏——海战棋
  • C++数据范围及字节对照表
  • 滑雪 详解(C++)
  • Vigenère密码(Day 1)详解
  • 表达式求值详解(C++)
  • 中缀表达式转化成后缀表达式
  • 小明的烦恼 详解(C++)
  • 唯一分解定理 详解(C++)
  • 迷瘴 详解(C++)
  • vector 详解(C++)
  • 二维数组 详解(C++)
  • 图 详解(C++)
  • 数据结构 详解(C++)
  • 文件复制 详解(C++)
  • 2014青岛初中组第2题 洪水 详解(C++)
  • 幂的后三位相同 详解(C++)
  • 字符串的查找删除 详解(C++)
  • 删数问题 详解(C++)
  • 文件操作 详解(freopen)(C++)
  • 判断数字在字符串中的位置 详解(C++)
  • 韩信点兵 详解(C++)
  • 八数码 详解(C++)
  • C++小游戏——迷宫
  • C++小游戏——24点
  • 边境线 详解(C++)
  • 挖金矿 详解(C++)
  • 回文数 详解(C++)
  • 龙虎斗 详解(C++)
  • 搜索(深度优先搜索与回溯) 经典例题题单+万字详解(C++)
  • 连接最大数 详解(C++)
  • 古希腊之争(一)详解(C++)
  • 比例化简 详解(C++)
  • 金币 详解(C++)
  • C++小游戏——小岛战争
  • C++小游戏——打方块
  • 螺旋矩阵 详解(C++)
  • Stamps 邮票问题 详解(C++)
  • 公交换乘 详解(C++)
  • 【图论】用链式前向星(邻接表)存有向图(图文代码逐句分析)
  • 【BFS】迷宫问题c++代码详解(逐句分析)
  • 【快速幂】a^b%p问题
  • 【DFS】n皇后问题(代码逐句分析)
  • 【快速乘与快速幂例题讲解】相乘取余爆long long?试试快速乘吧!
  • 【排列组合】只上代码不解释
  • 【题解专栏】南华大学19级软卓选拔赛题解
  • 【令人头秃的线段树】线段树入门题目详解(代码逐句分析)
  • 【数据结构】树状数组效果讲解
  • 【差分算法入门】例题讲解(代码逐句分析)
  • 【数据结构】并查集入门例题讲解(c++代码逐句分析)
  • 【数据结构】C++STL map 常见用法小结
  • 【图论】Dijkstra算法解决有向图最短路问题
  • 南华大学ACM队2021年7.14训练赛题解
  • 【动态规划】LIS最长上升子序列和LCS最长公共子序列
  • 【数据结构】KMP算法分析与理解(图文分析)
  • 【解题报告】动态规划进阶题(区间DP、树形DP、状压DP入门)
  • 【动态规划】数位DP入门题:不要62
  • 【图论】图的深度优先遍历与广度优先遍历(图文讲解)
  • 【图论】拓扑排序:一个名字高大上的实际很简单的算法(图文详解)
  • 【图论】Bellman_Ford算法求有步数限制的最短路(图文详解)
  • 【数据结构】图文详解Treap平衡树
  • 【图论】Spfa算法求最短路(长得像Dijkstra的,Bellman_Ford的优化算法)
  • 【图论】Floyd算法求任意两点间最短路
  • 【解题报告】图论基础练习(一)
  • 【紫书第五章】String、结构体、部分STL的常见用法
  • 【紫书第六章】链表(list)、栈和双向队列(deque)
  • 【紫书第六章】二叉树、欧拉图基本概念与性质
  • 【紫书第七章】暴力美学(能用暴力解决的事情为什么要动脑子?)
  • 【紫书第八章】算法的时间优化设计
  • 【紫书第九章】动态规划(DP)常见模型汇总与DP问题分析方法
  • 【紫书第十章】数论与概率入门
  • 【图论】Kruskal算法求最小生成树详解
  • 【紫书第十一章】图论模型与算法入门
  • 【图论】Prim算法求最小生成树详解
  • 【图论】染色法判定二分图详解
  • 【图论】用匈牙利算法找女朋友(纯爱党的大胜利)
  • 【数据结构】图文讲解神奇的单链表与双链表
  • 【解题报告】表达式求值(栈,表达式树)
  • 【解题报告】Jury Meeting (9.8CF div2)
  • 【数据结构】图文例题详解单调栈与单调队列
  • 【数据结构】堆的手动模拟实现
  • 【数据结构】可以逃课其它字符串算法的字符串哈希算法
  • 【图论】最优乘车(最短路变形)
  • 【图论】昂贵的聘礼(最短路变形)
  • 【排列组合、思维】Combinatorics Homework
  • 【图论】新年好(最短路的综合问题)
  • 【排序】动画演示10大排序算法
  • 【思维、费马小定理】CQXYM Count Permutations
  • 【二进制】Special Numbers
  • 【分层图最短路】通信线路
  • 【思维,暴力】奋发
  • 【数论】四则运算的取模处理
  • 【数据结构】线性处理字符串中指定字串的个数问题
  • 【动态规划】ST算法解决区间最值询问问题(RMQ问题)
  • hive应用实例 将查询结果写入原表中
  • hadoop2.4.1源码在64位系统编译过程中遇到的几个错误及解决方法
  • hadoop 升级
  • mongo性能测试demo 代码正确运行
  • sqoop简单的demo 先跑起来再说
  • python字典常见操作
  • java操作mysql实例 让代码跑起来
  • 反转字符串的多种方式-经典面试题系列
  • oracle instr函数 判断字段中是否有换行符
  • storm流式处理框架
  • hive partition 分区详解一
  • hive partition 分区详解二
  • NoSQL 数据库的使用场景
  • 列存储中常用的数据压缩算法
  • 数学公式排版测试
  • Linux服务器沦陷为肉鸡的全过程实录
  • 血腥!实况转播SQL注入全过程,让你知道危害有多大。
  • Web安全之SQL注入攻击技巧与防范
  • python基本文件操作
  • python处理文件效率对比awk
  • hive基本命令
  • hive 复合结构Map、Struct详解
  • ctr预估之特征工程
  • python解析配置文件
  • shell 计算代码运行时间
  • org.apache.hadoop.fs.ChecksumException: Checksum error
  • linux shell将字符串分割数组
  • awk 字符串替换 gsub
  • sed 替换
  • RSA 数字签名 免密码登录
  • shell判断字符串为空
  • shell 逐行读取文件
  • MongoDB最佳实践
  • 数据库事务ACID
  • hbase shell 入门
  • hive like与rlike的区别
  • PipeMapRed.waitOutputThreads(): subprocess failed with code N
  • 二分查找 python实现
  • sql语句查询执行顺序
  • python解析json串与正则匹配对比
  • python 正则匹配电话与ip
  • linux java Cannot allocate memory
  • python 正则表达 10分钟入门
  • MarkDown 行首缩进
  • vim批量删除与插入
  • vim 查找相同行 删除向同行
  • MapReduce Shuffle详解
  • awk去除行首行尾空格
  • awk去重
  • oracle 游标详解
  • oracle type rowtype详解
  • distinct 多列详解
  • VIM 高效操作
  • hive 正则表达式详解
  • python 正则表达式 \b 大坑
  • sublime批量添加注释
  • sublime实用快捷键 mac版
  • 利用RFM模型做电商客户价值分析
  • RFM模型分析
  • MySql explain命令详解
  • sed 常用命令
  • Python模块受欢迎排行榜Top200
  • svm多分类器详解
  • 使用消息队列的十大理由
  • logistic回归详解(二):损失函数(cost function)详解
  • python 浮点数精确运算解决方案
  • linux 统计文件的个数
  • java 读取配置文件的几种方法
  • 稀疏向量计算优化小结
  • java double转string
  • eclipse mac常用快捷键
  • hive udf开发超详细手把手教程
  • java class类
  • hive表加载数据的不同方式
  • BrightHouse存储引擎
  • 指数分布族(The Exponential Family)与广义线性回归(Generalized Linear Model GLM)
  • 程序运行过程浅析
  • azkaban 入门简介
  • 如何给awk传外部参数
  • linux shell 数字计算详解
  • mysql 优化 整体思路
  • python 迭代器与生成器 详解
  • 数据归一化小结
  • 插入排序 java实现
  • python random 生成随机数
  • python numpy模块玩转矩阵与科学计算
  • hadoop 注解之 interfaceAudience interfaceStability
  • hadoop 新API与旧API对比
  • hadoop mapper从源码开始 详解
  • git 远程仓库 remote 使用总结
  • linux mac tree 命令 总结
  • hadoop Configured Configrable Configuration Tool 源码详解
  • hadoop fs.trash 详解
  • Hadoop Configuration 源码详解
  • 基于sklearn 的one hot encoding
  • logistic回归详解(三):梯度下降训练方法
  • Hbase rowkey 设计原则
  • 信息熵 条件熵 信息增益 信息增益比 GINI系数
  • hadoop 压缩工具 比较
  • 二叉树 先序遍历 中序遍历 后续遍历 java实现
  • python sort sorted 排序详解
  • 用java数组实现栈
  • n的阶乘末尾含0的个数
  • 字符串全排列 java实现
  • 字符串 全组合
  • python GIL 全局锁
  • python 多线程 入门
  • 数据清洗与数据预处理浅析
  • python 两个list 求交集,并集,差集
  • 字符串旋转 不同解法
  • 快排 递归与非递归实现 优化
  • 统计单词个数 状态机方法
  • hive 时间函数 总结
  • 交换两个数 不使用中间变量
  • 数组中只出现一次的数
  • hive join 数据倾斜 真实案例
  • hive order by sort by distribute by总结
  • java 十进制与二进制,八进制,十六进制之间的转换
  • java 常用习惯用法总结
  • SQL操作结果集-并集,差集,交集,结果集排序
  • hadoop 代码中获取文件名
  • hive 窗口函数 应用场景与实战详解
  • awk 输出到多个文件 多路输出
  • 大数乘法与大数加法 java实现
  • 反转字符串 不同方式
  • python 嵌套list的一些小结
  • 递归 非递归 遍历二叉树
  • python 爬虫 爬取糗事百科段子
  • redis 实战系列(一)
  • redis 实战系列二:用python操作redis集群
  • hadoop 用MR实现join操作
  • eclipse一些实用小技巧
  • hadoop streaming 按字段排序与输出分割详解
  • Hadoop-Streaming实战经验及问题解决方法总结
  • java 中== equals hashcode源码剖析
  • 次导数 次梯度 小结
  • NP-Hard问题浅谈
  • SqlServer Convert函数 日期格式化
  • mac 启用与关闭root账户
  • spark 集群搭建 详细步骤
  • spark wordcount 实例
  • python lambda函数 与 函数式编程
  • Spark与Pandas中DataFrame的详细对比
  • 北美CS四大名校
  • Apache Parquet 与Apache ORC简介
  • spark sql 入门详解
  • scala 入门初探
  • mysql 修改root密码 修改账户登录host
  • spark MetaException(message:Version information not found in metastore. )
  • spark配置IntelliJ开发环境详解
  • RDD,DataFrame与DataSet区别
  • 深入浅出理解矩阵
  • SVD 详解 与 spark实战
  • kmeans算法详解与spark实战
  • LDA入门浅谈
  • CTR预估算法小结
  • CTR点击率预估实战分享
  • 链表常见操作java实现一:链表初始化,求链表长度
  • 链表常见操作java实现二:反转链表,从尾到头倒序遍历
  • 用牛顿迭代求方根
  • 从泰勒展开到牛顿迭代
  • 独立同分布(iid)随机变量的一些趣题
  • 漫谈Clustering:高斯混合模型(GMM)
  • RTB竞价中的cookie mapping技术
  • 泊松分布的前世今生
  • Java中的可变参数使用
  • java泛型通俗讲解
  • Rotate Array
  • shell 封装mysql查询
  • 编写可靠shell脚本的八个建议
  • 矩阵的一些常用结论
  • 从文本中随机选择百万行
  • 大数据工程师必备之蓄水池抽样算法
  • python json详解
  • python set类型
  • python中实用的collections模块
  • 用概率的方法计算Pi值
  • python的with用法
  • TensorFlow 安装教程
  • 批量重命名文件名
  • 企业级数据服务的一点感受
  • scala中map与flatMap浅析
  • scala中内部函数的使用
  • 你应该知道的RPC原理
  • 使用VirtualBox在Ubuntu下虚拟Windows XP共享文件夹设置方法(亲测)
  • ubuntu下安装win7虚拟机总结
  • chrome导入与导出书签
  • spark与hadoop对比
  • spark rdd详解一(rdd入门)
  • spark rdd详解二(transformation与action操作)
  • spark压缩和序列化相关
  • 有史以来最容易理解的控制反转(IoC)与注入依赖(DI)
  • 函数式编程( Functional)与命令式编程( Imperative)对比
  • scala 单例对象 伴生对象
  • python中的闭包与装饰器
  • scala 匿名函数
  • Output path is shared between the same module error
  • Avro, Protocol Buffers 、Thrift的联系与区别
  • 关于Hive数据仓库的那些事儿(一)模式设计
  • scala中一些常见用法
  • scala implicit隐式转化与隐式参数
  • java中操作时间
  • 分布式系统中的序列化与反序列化
  • hadoop文件的序列化
  • mllib线性回归GeneralizedLinearModel GeneralizedLinearAlgorithm源码解析
  • mllib逻辑回归LogisticRegressionWithLBFGS LogisticRegressionModel源码分析
  • java生成md5
  • InstantiationException in hadoop map reduce program
  • spark操作读取hbase实例
  • Thrift原理简析
  • 用maven骨架新建项目以及解决速度慢的问题
  • maven内置属性详细说明
  • maven生成可执行jar包
  • mapreduce多路输出实例
  • Intellij里面的几个异常处理方案
  • Java 中的枚举 (enum)
  • 统计某个字符串出现的次数
  • GeoHash距离大致估计
  • 使用匿名内部类排序对象
  • Double 中的 NAN与INFINITY
  • Hadoop Partitioner 实战详解
  • csdn中让图片居中
  • 判断一个点是否在多边形区域内
  • 判断一个数是否为质数
  • python中对象排序的两种方式
  • 异常点/离群点检测算法——LOF
  • mac上TK Framework double implementation
  • ETL调优的一些分享
  • 自学资料总结(持续更新)
  • MapReduce操作Hbase史上最完整范例
  • 一条拼了40min的hql引发的思考
  • git revert 回滚代码至上一版本
  • Scrapy ImportError: No module named items
  • python format 格式化输出
  • java.io.IOException: Filesystem closed
  • hive多行变一行
  • boost安装详细教程
  • python property 与get/set方法详解
  • linux 查看端口占用命令 亲测可用
  • java “lambda expressions not supported at this language level“
  • IntelliJ手动安装python与scala插件
  • shell判断文件与字符串
  • java 读取资源文件最详细解读
  • 数组与List的相互转换
  • java读取properties文件详解
  • maven解决依赖冲突
  • 单例模式(Singleton mode)实战讲解
  • 将netcat-openbsd替换成为netcat-traditional
  • 流动的推荐系统
  • 几个常用的shell脚本
  • scala 正则表达式
  • scala字符串变量替换
  • java获取键盘输入
  • Intellij mac快捷键
  • spark根据key输出到多个目录
  • 模式匹配的匿名函数
  • Comparable 与 Comparator 比较
  • 面试题链接总结
  • 作为Scala语法糖的设计模式
  • 设计模式之简单工厂模式,工厂方法模式,抽象工厂模式
  • Scala 用Option[T] 避免NullPointerException
  • scala中sorted,sortWith,sortBy用法详解
  • java常见基础面试题
  • java 不以科学记数法输出double
  • 二叉树反转java实现
  • scala中的apply方法与unapply方法
  • scala中实现break与continue功能
  • word2vec数学原理详解
  • combineByKey实例详解
  • 从内容/用户画像到如何做算法研发
  • 核函数(Kernel Function)与SVM
  • spark读取gz文件与parquet文件
  • anaconda升级sklearn版本
  • GBDT实战
  • Spark2.1特征处理:提取/转换/选择
  • spark生成DataFrame
  • sklearn 中GBDT的损失函数
  • scala中的柯里化函数
  • 函数成了一等公民
  • missing arguments for method toArray in trait Collection
  • spark aggregate函数详解
  • hadoop SequenceFile详解
  • java.lang.Exception: Test class should have exactly one public constructor
  • java泛型中的通配符 extends与super
  • python中的列表推导与生成器
  • Ensemble Learning方法总结
  • list的一些常见用法总结(实用干货收藏)
  • awk字符串匹配与传参
  • ubuntu修改默认root密码
  • spark 两个rdd求交集,差集,并集
  • spark中的广播变量与累加器
  • java泛型方法实现数值类型加法
  • scala实现数值类型加法
  • 通过释放cache内存解决ubuntu死机问题
  • 感知机(Perceptron)为什么不能表示异或(XOR)
  • Spark 堆外内存
  • Spark编程Tips
  • 单个id聚合
  • java集合的相互转化(map,set,list,array)
  • 神经网络之激活函数(activation function)
  • spark 通过打散热点key解决数据倾斜问题
  • 神经网络的直观解释相关文档
  • SparkSQL简单教程
  • linux shell中实现字符串反转的几种简单方法
  • Hbase KeyValue结构详解
  • java.lang.UnsupportedClassVersionError : Unsupported major.minor version 52.0
  • hive中的集合操作函数
  • 图像处理中的直方图与均衡化
  • Spark项目 error while loading <root>, error in opening zip file
  • kylin 系列介绍
  • scala中的作用域保护
  • java中的值传递与引用传递
  • ZooKeeper之ZkClient使用示例
  • java学习资料总结
  • spark 稀疏矩阵存储详细解读
  • 解决Intellij中的一些bug
  • spring boot中问题总结
  • Spring Boot中的事务管理与手把手实战
  • 使用curl与wget发送get与post请求
  • 负载均衡算法详解与实践
  • bagging boosting 随机森林 GBDT对比
  • git本地项目推动到gitlab远端服务器
  • \r \n \r\n的区别
  • 文本分类之一:语言模型
  • java异常处理中的返回值
  • Spark 按key聚合求平均值与占比
  • spark sortBy sortByKey实战详解
  • 入门级都能看懂的softmax详解
  • 求整数n次方以及矩阵n次方快速解法
  • 用matplotlib中的scatter方法画散点图
  • ubuntu升级tensorflow版本
  • 读取jar包中的资源文件
  • JAVA异常处理实战心得
  • Cannot load module file xxx.iml Intellij
  • git删除远程库文件
  • JetBrains(Intellij, pycharm)多行编辑模式
  • logistic回归详解(四):梯度下降训练逻辑回归python实现
  • 用梯度下降求解最小二乘线性回归python实现
  • windows传文件到linux
  • Git merge分支到master
  • python中字符编码:coding utf-8, unicde, defaultencoding, UnicodeDecodeError, UnicodeEncodeError
  • java,python,scala发送http请求
  • RuntimeError: failed to execute [‘dot‘, ‘-Tpdf‘, ‘-O‘, ‘test‘], make sure the Graphviz executables
  • 用递归求字符串的全组合
  • ubuntu .7z解压缩
  • 深度学习里的损失函数与交叉熵
  • python打平处理嵌套list
  • 硬币找零,最长上升子序列,背包问题等动态规划问题详解
  • python中type与isinstance异同
  • 二叉树递归非递归遍历,层次遍历,反转,输出路径等常见操作详细总结
  • 线性插值 多项式插值 样条插值 牛顿插值总结
  • 凸优化系列一:什么是最优化算法
  • 凸优化系列二:确定步长一维搜索算法
  • Builder创建者模式
  • java scala中传递变长参数
  • ? extends T 与 ? super T
  • sort colors 三色排序
  • Partition List 将链表分成两部分
  • Reverse Linked List 反转链表
  • ‘module‘ object has no attribute ‘computation‘
  • embedding lookup
  • 最长递增子序列(LIS longest-increment-subsequence)最长连续递增子序列 最大连续子序列和
  • 模拟微信发红包算法java实现
  • python zip函数小结
  • shell 查看空行与删除空行
  • java线程系列一:Thread类中的start()方法与run方法
  • MapReduce 1.x VS 2.x架构对比
  • 输出树的所有路径
  • Binary Tree Right Side View 二叉树右视图
  • Convert Sorted Array to Binary Search Tree(将有序数组转为二叉搜索树)
  • Path Sum Path Sum II
  • 给chrome手动安装github上插件
  • ImportError: /usr/lib/x86_64-linux-gnu/libstdc++.so.6: version `CXXABI_1.3.9‘ not found
  • numpy中的数组复制