过河卒,noip2003的题目过河卒

/*

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 <stdio.h>

#include <stdlib.h>

// 当前需要的维度，可以修改这个值进行扩展（不用改动算法）

#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;i<DIMENSION;i++)

{

// 在维度 i 上距离不为 0 ，需要计算最小移动单位

if(distance[i] != 0)

{

steps[*stepsAmount].index = i;

steps[*stepsAmount].d = distance[i]>0 ? 1 : -1;

(*stepsAmount) ++;

}

}

}

// 打印最小移动单位

void printStep(const struct Step* step)

{

int i;

// 对于小于等于二维的坐标系，可以为每一步指定上下左右四个方向

if(DIMENSION <= 2)

{

if(step->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;i<DIMENSION;i++)

{

printf("%d",i==step->index ? 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<DIMENSION;i++)

d += abs(distance[i]);

if(d == 0)

{// 已经走完全程，输出路径

for(i=0;i<pathLength;i++)

{

printStep(&path[i]);

if(i!=(pathLength-1))

printf(" ==> ");

else

printf("\n");

}

// 统计路径条数

(*totalSchemeAmount) ++;

}

else

{

// 获取最小移动单位

getSteps(distance,steps,&stepsAmount);

for(i=0;i<stepsAmount;i++)

{

// 任选一个维度，运动一个最小单位

path[pathLength++] = steps[i];

distance[steps[i].index] -= steps[i].d;

// 解决成子问题

getPath(distance,path,pathLength,totalSchemeAmount);

// 回溯

pathLength--;

distance[steps[i].index] += steps[i].d;

}

}

}

int main(int argc, char *argv[])

{

/* DIMENSION = 1 */

//int distance[DIMENSION]={-5};

/* DIMENSION = 2 */

int distance[DIMENSION]={8,4};

/* DIMENSION = 3 */

//int distance[DIMENSION]={1,1,1};

struct Step steps[DIMENSION],path[DIMENSION*MAX_LENGTH_PER_DIMENSION];

int stepsAmount,totalSchemeAmount=0;

// 计算路径

getPath(distance,path,0,&totalSchemeAmount);

printf("一共 %d 条路径。\n",totalSchemeAmount);

return 0;

}

-

下面是更多关于过河卒的问答

C语是没有了，C++的倒是自己参考

思想很简单，分略。

void printPath(const vector<bool>& path)

{

for(unsigned i = 0; i < path.size(); i++)

{

cout << (path[i] ? ("move down") : ("move right")) << " > ";

}

cout << endl;

}

void enumMove(vector<bool>& path, unsigned startPos, unsigned downLeft)

{

--downLeft;

for (unsigned i = startPos; i < path.size(); i++)

{

path[i] = true;

if (downLeft)

{

enumMove(path, i + 1, downLeft);

}

else

{

printPath(path);

}

path[i] = false;

}

}

int main()

{

vector<bool> initPath(12, false);

enumMove(initPath, 0, 4);

system("pause");

return 0;

} 本回答被网友采纳 五条路，很好数的。我是看放大图的，好像跟小图有些出入。

此题较简单，dp解决。态规划）

动码如下：

var a,b,i,j:longint;
    e:array[-2..22,-2..22] of int64;
begin
  readln(a,b);
  e[0,-1]:=1;
  for i:=0 to a-1 do
    for j:=0 to b-1 do
        e[i,j]:=e[i-1,j]+e[i,j-1];
  writeln(e[a-1,b-1]);
end.

递推

f[i][j]=f[i-1][j]+f[i][j-1]表示卒在(i,j)是从或者上到的，那卒到(i,j)有几种走法当然是 左边和上边的走法数相加了。

for (i=1;i<=a && safe(x,y,i,0);i++) f[i][0]=1;

for (j=1;j<=b && safe(x,y,0,j);j++) f[0][j]=1;

这两句是边缘的情况处理，因为边缘的点只能由一个方向走到。

safe函数看2楼的解释，非常详细。

以后碰到这种题，想想它前后的联系，就是它怎么到达这点的，自然迎刃而解了

Tags：过河卒,简单过河卒问题,noip2003的题目过河卒

转载：文章来自用户投稿不代表本站观点，如有侵权请联系我们。