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;