import java.util.HashMap;
import java.util.Map;
/**
* 思路:到达{M,N}坐标的路径数 = 到达{M-1,N}的路径数 + 到达{M,N-1}的路径数
* 利用容器MAP,存储到达{x,y}的路径数,可以避免一些重复计算,提高效率
*
* @author xiaojianhx
* @date 2012-10-19
*/
public class Demo {
/** X坐标 */
private int maxX;
/** Y坐标 */
private int maxY;
/** 马的位置坐标 */
private int[] c_axis;
/** 马跳一步可到达的点坐标 */
private int[][] ma;
/** 到达某坐标的路径树 */
private Map<String, Long> data = new HashMap<String, Long>();
/**
* 获取结果
*
* @param b_axis
* 最大位置坐标
* @param c_axis
* 马的位置坐标
* @return Long 原点到达最大位置的路径数
*/
public Long getResult(int[] b_axis, int[] c_axis) {
// 初始化
init(b_axis, c_axis);
return getCount(maxX, maxY);
}
/**
* 初始化
*
* @param b_axis
* 最大坐标
* @param c_axis
* 马的位置坐标
*/
private void init(int[] b_axis, int[] c_axis) {
maxX = b_axis[0];
maxY = b_axis[1];
this.c_axis = c_axis;
// 初始化马跳一步可到达的点坐标
initMa();
}
/**
* 马跳一步可到达的点坐标
*/
private void initMa() {
ma = new int[maxX + 1][maxY + 1];
for (int i = 0; i <= maxX; i++) {
for (int j = 0; j <= maxY; j++) {
if (isMa(i, j)) {
ma[i][j] = -1;
} else {
ma[i][j] = 0;
}
}
}
}
/**
* 该点马跳一步,是否可到达
* <li>横纵坐标的差的绝对值为1和2</li>
* <li>包括马的原始位置</li>
*
* @param x
* X坐标
* @param y
* Y坐标
* @return boolean 该点马跳一步,是否可到达 TRUE:可到达;FALSE:不可到达
*/
private boolean isMa(int x, int y) {
int tmpX = Math.abs(x - c_axis[0]);
int tmpY = Math.abs(y - c_axis[1]);
if (tmpX == 1 && tmpY == 2) {
return true;
}
if (tmpX == 2 && tmpY == 1) {
return true;
}
return tmpX == 0 && tmpY == 0;
}
/**
* 计算到达{x,y}的路径数
*
* @param x
* X坐标
* @param y
* Y坐标
* @return Long 到达{x,y}的路径数
*/
private Long getCount(int x, int y) {
// 结束条件:如果{x,y}小于原点,或者为马点,记为0,退出
if (check(x, y)) {
return 0L;
}
// 结束条件:到达原点,记为1
if (x == 0 && y == 0) {
return 1L;
}
// MAP中获取到达{x-1,y}的路径数
Long value0 = data.get((x - 1) + "," + y);
// MAP中获取到达{x,y-1}的路径数
Long value1 = data.get(x + "," + (y - 1));
// 如果为空,则需要重新计算,(此处可大大提高执行效率)
value0 = getCount(x - 1, y, value0);
value1 = getCount(x, y - 1, value1);
// 到达{x,y}坐标的路径数 = 到达{x-1,y}的路径数 + 到达{x,y-1}的路径数,并保存到MAP,供其他使用
Long c = value0 + value1;
data.put(x + "," + y, c);
return c;
}
/**
* 获取Y的值
*
* @param x
* X坐标
* @param y
* Y坐标
* @param val
* 到达{x,y}的路径数
* @return Long 到达{x,y}的路径数
*/
private Long getCount(int x, int y, Long val) {
return val != null ? val : getCount(x, y);
}
/**
* 校验是否符合退出条件
* <li>{x,y}坐标小于原点</li>
* <li>{x,y}为马点</li>
*
* @param x
* X坐标
* @param y
* Y坐标
* @return boolean 验是否符合退出条件 TRUE:是;FALSE:不是
*/
private boolean check(int x, int y) {
return x < 0 || y < 0 || ma[x][y] == -1;
}
public static void main(String[] args) {
for (int i = 1; i <= 30; i++) {
long l0 = System.currentTimeMillis();
int[] b_axis = { i, i };
int[] c_axis = { 3, 2 };
long count = new Demo().getResult(b_axis, c_axis);
long l1 = System.currentTimeMillis();
System.out.println("{" + i + "," + i + "}:用时" + (l1 - l0) + "[MS],路径数" + count);
}
}
}
{1,1}:用时15[MS],路径数0
{2,2}:用时0[MS],路径数1
{3,3}:用时0[MS],路径数1
{4,4}:用时0[MS],路径数0
{5,5}:用时0[MS],路径数3
{6,6}:用时0[MS],路径数17
{7,7}:用时0[MS],路径数79
{8,8}:用时0[MS],路径数341
{9,9}:用时0[MS],路径数1420
{10,10}:用时0[MS],路径数5797
{11,11}:用时0[MS],路径数23387
{12,12}:用时0[MS],路径数93652
{13,13}:用时16[MS],路径数373218
{14,14}:用时0[MS],路径数1482570
{15,15}:用时0[MS],路径数5876662
{16,16}:用时0[MS],路径数23260199
{17,17}:用时0[MS],路径数91975390
{18,18}:用时0[MS],路径数363455085
{19,19}:用时0[MS],路径数1435667475
{20,20}:用时0[MS],路径数5669633400
{21,21}:用时0[MS],路径数22387608210
{22,22}:用时0[MS],路径数88399757790
{23,23}:用时16[MS],路径数349070903010
{24,24}:用时0[MS],路径数1378530151050
{25,25}:用时0[MS],路径数5444701787616
{26,26}:用时0[MS],路径数21507902567778
{27,27}:用时0[MS],路径数84975924943774
{28,28}:用时0[MS],路径数335794021531576
{29,29}:用时0[MS],路径数1327188954058100
{30,30}:用时0[MS],路径数5246593689252916
分享到:
相关推荐
本课程主要讲解了如何使用C++解决一种基于棋盘游戏的算法问题,称为"马拦过河卒"。这个问题源自于国际象棋的规则,涉及到棋子的移动路径计算。在这个问题中,我们需要计算卒从起始位置A到达目标位置B的路径数量,...
在本资源中,我们主要关注的是使用C语言实现算法的解答,这涵盖了算法的第1到第4个部分。C语言是一种广泛用于系统编程、应用编程、嵌入式系统以及编写算法实现的强大编程语言。其简洁性和高效性使得它成为学习和理解...
这个压缩包“算法:C语言实现(第1~4部分)源代码”显然包含了使用C语言编写的算法实现,可能是针对数据结构(Data Structures)的基础知识,以及一些基础到进阶的算法。 首先,我们可以从"DS_C"这个压缩包子文件的...
算法:C语言实现(第1~5部分)源代码+勘误 算法:C语言实现(第1~5部分)源代码+勘误 算法:C语言实现(第1~5部分)源代码+勘误 算法:C语言实现(第1~5部分)源代码+勘误 算法:C语言实现(第1~5部分)源代码+勘误
本文将讲解如何使用快速排序算法从25匹马中选出最快的三匹马,并对相关的数据结构和算法进行详细的解释。 快速排序算法概述 快速排序算法是一种基于比较的排序算法,它的时间复杂度为O(n log n),是目前已知的最快...
二值化算法:Otsu算法、Bernsen算法、Niblack算法、循环阈值算法、迭代二值化算法等matlab代码,入门级
在SAR成像处理中,有三种重要的算法:Range-Doppler (RD)、Random Migration Algorithm (RMA) 和 Compressive Sensing (CS)。下面将详细介绍这三种算法及其应用。 1. Range-Doppler (RD) 算法: RD算法是SAR成像的...
4. **图论算法**:包括最短路径算法(如Dijkstra算法和Floyd-Warshall算法)、拓扑排序和最小生成树算法(如Prim和Kruskal算法),这些都是解决复杂网络问题的关键工具。 5. **动态规划**:通过构建状态转移方程,...
1. 排序算法:包括冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等,理解它们的工作原理和时间复杂度是至关重要的。 2. 搜索算法:二分查找、线性查找、深度优先搜索(DFS)和广度优先搜索(BFS)是...
算法经典书籍 普林斯顿大学教授大作,用c++描述,利于学习算法及c++
《MATLAB优化算法案例分析与应用》 MATLAB中文论坛鼎力支持,提供 在线交流,有问必答 网络互动答疑服务 详解34个工程应用案例、29个算法案例和34种算法应用 详解12种常用数据处理算法:灰色关联、偏zui小二乘回归、...
### 数据结构与算法(Python) #### 核心知识点解析 ##### 一、算法效率与时间复杂度 **算法效率**是指算法完成特定任务所需资源(如时间或空间)的多少。在评估算法效率时,一个重要的概念是**时间复杂度**,它...
1. 排序算法: - 冒泡排序:基础排序算法,通过不断交换相邻的不正确顺序元素进行排序。 - 选择排序:每次找到未排序部分的最小元素并放置在已排序部分的末尾。 - 插入排序:将未排序的元素逐个插入到已排序部分...
3. 边缘检测算法:该算法使用 Sobel 算法来检测黑线的边缘。Sobel 算法是一种常用的边缘检测算法,可以检测图像中的水平、垂直和对角线边缘。 4. 阈值分割算法:该算法使用阈值分割算法来提取黑线。阈值分割算法...
A星(A*)算法是一种在图形搜索问题中广泛应用的路径搜索算法,它结合了最佳优先搜索(如Dijkstra算法)和启发式搜索(如贪婪最佳优先搜索)的优点。A星算法通过使用一个评估函数来预测从当前节点到目标节点的总成本...
本资源“各种自适应算法的matlab仿真”聚焦于利用MATLAB这一强大的数值计算和仿真工具来演示和理解五种核心的自适应算法:LMS(Least Mean Squares)、NLMS(Normalized LMS)、VSLMS(Variable Step Size LMS)、...
书中第一章便介绍了回溯法,这是一种通过递归方式在解空间树中搜索问题解的算法,它在解决“马拦过河卒”这样的路径规划问题时,显得尤为有效。在“马拦过河卒”问题中,我们需要计算一个卒从棋盘上的A点移动到B点的...
- 动态规划和贪心算法都属于递推算法的一种,都试图通过找到一系列局部最优解来构建全局最优解。 **区别:** - **贪心算法**的特点在于每一步的选择都是局部最优的,并且一旦做出决策就不会更改。这意味着每一步的...
本书《算法心得:高效算法的奥秘》由一位在IBM工作超过50年的资深计算机专家撰写,是算法领域具有重要影响力的著作之一。根据描述,书中系统性地介绍了高效、优雅且巧妙的算法,并从数学的角度对这些算法背后的原理...
马走日棋盘算法 马走日棋盘算法是计算机科学领域中的一种经典问题,旨在寻找一条可行的路径,使得棋子“马”能走遍棋盘上的所有落子点,而每个落子点只能走一次。该算法的实现需要解决两个关键问题:如何表示棋盘和...