Horace7 level
获赞
372
粉丝
2
关注
1
看过 TA
18
伦敦大学学院
2019
Java
IP属地:未知
暂未填写个人简介
私信
关注
2017-12-01 21:53
已编辑
伦敦大学学院 Java
** 在一个n * m的棋盘上,有两只“马”,这里的马指的是中国象棋里的马,现在想要让这两只马跳到指定的位置。问最少需要的步数。 H表示马,h表示想要跳到的位置,#表示有别的棋子,*表示空位。 示例: 棋盘: H**h* **h** **H## ##*** ***** 最少需要的步数:2 顺便问问给的三道题只写出两道,两道中其中一道还不是最优解...是不是凉了?大家面过拼多多的电话面试的一面后多久有后续通知呀? //补充:写了很久,写了个很长的答案,希望大佬们斧正,见楼下
温温:感觉思路还是比较简单的,我们可以将马分为A,B,要跳的位置分为a,b 行走策略 可以用反证法证明一匹马先走,另一匹马后走,与不规定马走的顺序的最优解相等。 因此,根据马和地方的不同,我们将问题分为四个小问题,即: A马先走到a点,然后B马走到b点 A马先走到b点,然后B马走到a点 B马先走到a点,然后A马走到b点 B马先走到b点,然后A马走到a点 分别求以上四个小问题的最优解,然后再从四个小问题的解中选取最优解即可。 算法 这里算法是要设计给定一个图,一匹马,一个目的地,求马到达该点的最短跳数。 方法就是和上面几个人的说法一致,用BFS即可,另用一张表记录马跳到当前该点最短跳数。
投递拼多多集团-PDD等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务