A点有一个卒,需要走到目标B点.行走规则：可以向下（共4步）或者向右（共8步）.要求计算从A能够到达B的路径的条数,并输出每一条路径.

A点有一个卒,需要走到目标B点.行走规则：可以向下（共4步）或者向右（共8步）.要求计算从A能够到达B的路径的条数,并输出每一条路径.
A点有一个卒,需要走到目标B点.行走规则：可以向下（共4步）或者向右（共8步）.要求计算从A能够到达B的路径的条数,并输出每一条路径.

A点有一个卒,需要走到目标B点.行走规则：可以向下（共4步）或者向右（共8步）.要求计算从A能够到达B的路径的条数,并输出每一条路径.
/*
A点有一个卒,需要走到目标B点.行走规则：可以向下（共4步）或者向右（共8步）.
要求计算从A能够到达B的路径的条数,并输出每一条路径.
题目描述的是一种在二维空间中情形.设 X 轴为从左到右,Y轴为从上到下.
有 A 和 B 两点,第 1 维(X轴)距离d[1]=8,第 2 维（Y轴）距离 d[2]=8,
因此沿着点A到点B的向量为(8,4) .每次沿着向量的一个方向（X轴或Y轴）运动一个单位,
也就是每次可以移到（1,0）或者(0,1).计算从A到达B的路径条数.
一般的情形是：
在 D 维空间中,有A,B两点,
这两点在第 1 维距离d[1],第 2 维距离d[2],...,第D维的距离d[D],
因此沿着点A到点B的向量为(d[1],d[2],...,d[D]).每次沿着向量的一个方向运动一个单位,
也就是每次可以移动(±1,0,...,0)或者(0,±1,...,0),...,或者(0,0,...,±1),
这里的第 i 个 ±1,实际只能取+1或者-1,具体正负性和相应的 d[i] 一样.
计算从A到达B的路径条数.
解决的方案：
我们针对题目描述的二维空间的情形进行分析.
点A到点B的向量为(8,4) 定下来后,因为每次只能沿着向量的一个方向（X轴或Y轴）运动一个单位,
而这两个方向是正交的,也就是互不影响的.
不管先走X方向,还是先走Y方向,最后都一定是向X方向走 8 步,向 Y 方向走 4 步.
假设开始沿 X 方向运动一个单位,我们假设到达了点 A' .
那么点 A' 到点 B 的向量为(7,4) ,下面问题就是计算 A' 到达 B 的路径条数.
可以发现,问题“计算 A 到达 B 的路径条数”和问题“计算 A 到达 B 的路径条数”是同一类问题.
假设开始沿 Y 方向运动一个单位,我们假设到达了点 A'' .
那么点 A'' 到点 B 的向量为(8,3) ,下面问题就是计算 A'' 到达 B 的路径条数.
可以发现,问题“计算 A 到达 B 的路径条数”和问题“计算 A'' 到达 B 的路径条数”是同一类问题.
通过上面的两个假设可以发现,不管第一步怎么走,接下来都产生了一个相似的子问题.
这就是分治的策略,也就是把一个大问题,分解成若干个相似的子问题.
上面的两个假设,最后的一个子问题必定是某点到 B 的向量为(1,0),
或者某点到 B 的向量为(0,1),这是能立即解决的子问题.
*/
#include
#include
// 当前需要的维度,可以修改这个值进行扩展（不用改动算法）
#define DIMENSION 2
// 每个维度的最大长度
#define MAX_LENGTH_PER_DIMENSION 100
// 空间最小的移动向量.一次只能在一个维度移动一个单位.
struct Step
{
// 维度索引
int index;
// 移动距离
int d;
};
/*
根据向量距离 distance ,计算每个维度上的最小移动单位.
通过 steps 和 stepsAmount 返回.
注意：如果向量距离某个维度上的的距离为 0 ,那么这个维度上不会返回最小移动单位.
*/
void getSteps(int distance[],struct Step steps[],int *stepsAmount)
{
int i;
*stepsAmount=0;
for(i=0;i0 1 :-1;
(*stepsAmount) ++;
}
}
}
// 打印最小移动单位
void printStep(const struct Step* step)
{
int i;
// 对于小于等于二维的坐标系,可以为每一步指定上下左右四个方向
if(DIMENSION index == 0)
{
if(step->d > 0)
printf("右");
else
printf("左");
}
else if(step->index == 1)
{
if(step->d > 0)
printf("下");
else
printf("上");
}
}
// 对于大于二维的坐标系,直接输出移动向量.
else
{
printf("[");
for(i=0;iindex step->d :0);
if(i != DIMENSION-1)
printf(",");
}
printf("]");
}
}
void getPath(int distance[],
struct Step path[],int pathLength,int *totalSchemeAmount)
{
int i,j,k,d;
struct Step steps[DIMENSION];
int stepsAmount;
// 计算需要移动的总距离
for(i=0,d=0;i