0%

WayCount

算法导论练习题

有一个机器人,从S出发到E去,只能向右或向下走,X表示该格子不能走。问从S到E共有多少种走法。

S
X X
X X
X E
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int main()
{
int a[8][12] = {
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,1,1,1,1,1,1,1,0,},
{0,1,1,0,1,1,1,1,1,0,1,0},
{0,1,1,1,1,1,1,1,1,1,1,0},
{0,1,1,1,0,1,1,0,1,1,1,0},
{0,1,1,1,1,1,1,1,1,1,1,0},
{0,1,1,1,1,1,1,1,0,1,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0} };
int b[8][12];
for (int i = 1; i <= 6; i++)
for (int j = 1; j <= 10; j++)
b[i][j] = a[i][j];
for (int i = 2; i <=6; i++)
{
for (int j = 2; j <=10; j++)
{
if(a[i][j])
b[i][j] = b[i - 1][j] + b[i][j - 1];

}
}
for (int i = 1; i <= 6; i++)
{
for (int j = 1; j <= 10; j++)
cout << setw(4)<<b[i][j];
cout << endl;
}
system("pause");
return 0;
}