在m行n列的棋盘地上有一个m行和n列棋子，它走“日”，且只能向右走。现在它位于（1,a）处（1<=a<=m

来源：蜘蛛抓取(WebSpider) 时间：2019-12-16 00:50 标签： 地上有一个m行和n列

下过象棋的人都知道马只能走'ㄖ'字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘，棋盘的左下角有一匹马请你计算至少需要几步可以将它移动到棋盤的右上角，若无法走到则输出-1.如n=1，m=2,则至少需要1步；若n=1m=3,则输出-1。

马走日从某一点开始走，一共有8种走法：

题目要求从左下走到右上那么能用上的就是坐标轴第一和第四象限的4种走法，需要根据实际位置判断马下一步怎么走而且走的总步数最少，需要使用广度优先遍历从某一步到下一步的所有走的路径还需要记录步长，考虑最短路径 算法能力比较差，代码的具体编写没写出来

这是关于这道题嘚解题报告：

里面的思路有给广度优先加剪枝的，还有用向量的但是有4层for循环复杂度太高。

希望可以帮忙分析下这道题谢谢大家。

在一个m*n的棋盘上有k个格子里放有棋子。是否总能对所有棋子进

该楼层疑似违规已被系统折叠 

在一个m*n的棋盤上有k个格子里放有棋子。是否总能对所有棋子进行红蓝二染色使得每行每列的红色棋子和蓝色棋子最多差一个？


该楼层疑似违规已被系统折叠 

可以建一个二分图G(X,Y)，其中X有m个顶点代表了棋盘的m个行Y有n个顶点代表了棋盘的n个列。第i行第j列有棋子就在X(i)和Y(j)之间连一条边先找出图G里的所有环（由于是二分图，环的长度一定是偶数）把环里的边红蓝交替染色。剩下的没染色的图一定是一些树对每棵树递歸地进行操作：去掉一个叶子节点和对应边，把剩下的树进行合法的红蓝二染色再把刚才去掉的顶点和边加回去，给这个边适当的颜色鉯满足要求


我要回帖

更多关于 地上有一个m行和n列 的文章

 

随机推荐