c语言过河卒,c语言过河卒详细解析

本文目录一览：

• 1、名称：马拦过河卒问题
• 2、简单过河卒问题
• 3、C语言 马拦过河卒 我想用 二维数组递推出来。。为什么提交上就是不对呢？
• 4、c++马拦过河卒
• 5、C语言递推例题过河卒，样例输入6 6 3 2，样例输出17，帮我看看我程序的问题，答案错误。
• 6、马拦过河卒 C语言

名称：马拦过河卒问题

program ex1(input,output);

const

dx: array[1 .. 8] of Shortint = (-2, -1, 1, 2, 2, 1, -1, -2);

dy: array[1 .. 8] of Shortint = (1, 2, 2, 1, -1, -2, -2, -1);

var

n, m, x, y, i, j: Byte;

g: array[0 .. 20, 0 .. 20] of Byte;

f: array[0 .. 20, 0 .. 20] of Comp;

begin

Readln(n, m, x, y);

Fillchar(g, Sizeof(g), 0);

g[x, y] := 1;

for i := 1 to 8 do

if (x + dx[i] = 0) and (x + dx[i] = n) and

(y + dy[i] = 0) and (y + dy[i] = m) then

g[x + dx[i], y + dy[i]] := 1;

f[0, 0] := 1;

for i := 1 to n do

if g[i, 0] = 0 then f[i, 0] := f[i – 1, 0];

for i := 1 to m do

if g[0, i] = 0 then f[0, i] := f[0, i – 1];

for i := 1 to n do

for j := 1 to m do

if g[i, j] = 0 then f[i, j] := f[i – 1, j] + f[i, j – 1];

Writeln(f[n, m]: 0: 0)

end.

我不会C，自己看了后改吧

简单过河卒问题

/*

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

d += abs(distance[i]);

if(d == 0)

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

for(i=0;ipathLength;i++)

{

printStep(path[i]);

if(i!=(pathLength-1))

printf(” == “);

else

printf(“\n”);

}

// 统计路径条数

(*totalSchemeAmount) ++;

}

else

{

// 获取最小移动单位

getSteps(distance,steps,stepsAmount);

for(i=0;istepsAmount;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语言 马拦过河卒 我想用 二维数组递推出来。。为什么提交上就是不对呢？

看了这个题，怎么感觉我的问题比你的还要多呢，

1.a b c d 输入的分别是什么？

2.棋盘上的0和1分别代表什么？

3.棋盘未初始化，你知道那些未被赋值的格格都是些什么值吗？数组p[][]为什么不给初始化呢？

4.每一个语句都语法不错，都简单之极，就是组合起来不知所谓，可以加点注释解释一下吗?应用是什么规则? 我读了N遍还是不理解你在做什么

c++马拦过河卒

#includeiostream

using namespace std;

int const Max = 16;

int dir[][2] = { { 1, 0 }, { 0, 1 } } ;

int dp[Max][Max] = { 0 };

int k = 0; //计数器

struct Point {

    int x, y;

};

Point b, horse;

bool onboard(int x, int y) {

    return x=0  xMax  y=0  yMax;

}

void on(int x, int y) //将马附近的坐标记作1

{

    if(onboard(x,y)) dp[x][y] = 1;

    if(onboard(x-2,y-1)) dp[x – 2][y – 1] = 1;

    if(onboard(x-2,y+1)) dp[x – 2][y + 1] = 1;

    if(onboard(x+2,y-1)) dp[x + 2][y – 1] = 1;

    if(onboard(x+2,y+1)) dp[x + 2][y + 1] = 1;

    if(onboard(x-1,y-2)) dp[x – 1][y – 2] = 1;

    if(onboard(x-1,y+2)) dp[x – 1][y + 2] = 1;

    if(onboard(x+1,y-2)) dp[x + 1][y – 2] = 1;

    if(onboard(x+1,y+2)) dp[x + 1][y + 2] = 1;

}

void dfs(int x, int y) {

    if(x  b.x || y  b.y) return; // 如果提速，加上这行

    if (x == b.x  y == b.y) {

        ++k;

        return;

    }

    for (int i = 0; i  2; i++) {

        int IX = x + dir[i][0];

        int IY = y + dir[i][1];

        if (onboard(IX, IY)) {

            if (dp[IX][IY] == 0) {

                dfs(IX, IY);

            }

        }

    }

}

int main() {

    cin  b.x  b.y  horse.x  horse.y;

    on(horse.x, horse.y);

    dfs(0, 0);

    cout  k;

}

#includeiostream

using namespace std;

int const Max = 16;

int const dir[][2] = { { 1, 0 }, { 0, 1 } } ;

int dp[Max][Max] = { 0 };

int k = 0; //计数器

struct Point {

    int x, y;

};

Point b, horse;

bool onboard(Point p) {

    return p.x=0  p.xMax  p.y=0  p.yMax;

}

void on(Point p) //将马附近的坐标记作1

{

    int x = p.x, y = p.y;

    if(onboard({x,y})) dp[x][y] = 1;

    if(onboard({x-2,y-1})) dp[x – 2][y – 1] = 1;

    if(onboard({x-2,y+1})) dp[x – 2][y + 1] = 1;

    if(onboard({x+2,y-1})) dp[x + 2][y – 1] = 1;

    if(onboard({x+2,y+1})) dp[x + 2][y + 1] = 1;

    if(onboard({x-1,y-2})) dp[x – 1][y – 2] = 1;

    if(onboard({x-1,y+2})) dp[x – 1][y + 2] = 1;

    if(onboard({x+1,y-2})) dp[x + 1][y – 2] = 1;

    if(onboard({x+1,y+2})) dp[x + 1][y + 2] = 1;

}

void dfs(Point current) {

    int x = current.x, y = current.y;

    if(x  b.x || y  b.y) return; // 如果提速，加上这行

    if (x == b.x  y == b.y) {

        ++k;

        return;

    }

    for (int i = 0; i  2; i++) {

        int IX = x + dir[i][0];

        int IY = y + dir[i][1];

        if (onboard({IX, IY})) {

            if (dp[IX][IY] == 0) {

                dfs({IX, IY});

            }

        }

    }

}

int main() {

    cin  b.x  b.y  horse.x  horse.y;

    on(horse);

    dfs({0, 0});

    cout  k;

}

C语言递推例题过河卒，样例输入6 6 3 2，样例输出17，帮我看看我程序的问题，答案错误。

对第一行或者第一列的初始化值不能简单的全部初始化为1。

比如说样例中的马的位置是在（3，2）所以（2,0）这个点是不可达的。由于卒只能向下和向右走，（2,0）之下的所有的点都是不可达的。所以你的答案会错。

int main()

{

int n,m,x,y,i,j,t,h,l;

long long a[100][100],b[100][100];

scanf(“%d%d%d%d”,n,m,x,y);

for(i=0; i=n; i++)

{

for(j=0; j=m; j++)

{

if((i==xj==y)||(i==x-2j==y-1)||(i==x-2j==y+1)||(i==x-1j==y-2)||(i==x-1j==y+2)||(i==x+1j==y-2)||(i==x+1j==y+2)||(i==x+2j==y-1)||(i==x+2j==y+1))

{

b[i][j]=0;

}

else

{

b[i][j]=1;

}

}

}

for(h=0; h=n; h++)

{

for(l=0; l=m; l++)

{

if(b[h][l]==1)

{

if(h==0 l==0)

a[h][l]=1;

else if(h == 0)

a[h][l] = a[h][l-1];

else if(l == 0)

a[h][l] = a[h-1][l];

else

a[h][l]=a[h][l-1]+a[h-1][l];

}

else

a[h][l]=0;

}

}

printf(“%d”,a[n][m]);

return 0;

}

马拦过河卒 C语言

把下面这段检查下，x-1,x-2,y-1,y-2是否有越界？

map[x][y]=0; map[x-1][y-2]=0; map[x-1][y+2]=0; map[x+1][y-2]=0; map[x+1][y+2]=0; map[x-2][y-1]=0; map[x-2][y+1]=0; map[x+2][y-1]=0; map[x+2][y+1]=0;