看看你能不能答出来 最好写上详细思路 能写代码更好

怎么插入图片啊
那个控件怎么好像没反应？
手动打出来了。。。
  |——|——|——|——|B
  |    |   |    |   |
  |——|——|——|——|
  |    |   |    |   |
  |——|——|——|——|
  |    |   |    |   |
  |——|——|——|——|
  |    |   |    |   |
 A|——|——|——|——|

问从A到B可能有多少种走法
是一个4*4的方格阵，手动打的，不太齐整。

10 个解决方案

#1

动态规划

#2

问题描述

Yipeng有一头非常聪明的奶牛，这头奶牛有一个强烈的愿望就是去上学，yipeng决定同意他的请求。奶
牛的出发地是左下角坐标（1，1），学校坐标为右上角（m, n），这里我们只考虑整数点坐标。奶牛要
从左下走到右上，每次只能向右或向上走一个单位，即穿过一条道路。有一些坐标是不可到的，有一些
是可以到达的。Yipeng想考考这个聪明的奶牛，就问它每天上学一共有多少种不同的路径可以选择？两
条路径不同当两条道路至少有一条非公共道路。

问题输入

首先一个整数t表示测试数据组数（1=<t<=30）,对每组数据都有两个整数m, n (1<=m, n<=15)表示学校
的坐标，然后是m*n的矩阵，第i行第j个数代表坐标为（i，j）处的坐标是不是可达，1代表可达，0代
表不可达。数据保证起点和终点可达。

问题输出

每组测试数据输出一行，每行一个整数，表示奶牛可以选择的上学路径数。如果没有路径能让奶牛上学
则输出0。

样例输入

1
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

20

#include <stdio.h>
int mark[31][31];
int sol[31][31];

int solve(int n, int m)
{
	int i, j;
	sol[1][1] = 1;
	for (i = 2; i <= m; ++i)
		if (mark[1][i]) sol[1][i] = sol[1][i-1];
		else sol[1][i] = 0;
	for (i = 2; i <= n; ++i)
		if (mark[i][1]) sol[i][1] = sol[i-1][1];
		else sol[i][1] = 0;
	for (i = 2; i <= n; ++i)
		for (j = 2; j <= m; ++j)
		if (mark[i][j]) sol[i][j] = sol[i-1][j]+sol[i][j-1];
		else sol[i][j] = 0;
	return sol[n][m];
}

int main(void)
{
	int cnt;
	scanf("%d", &cnt);
	while (cnt--)
	{
		int n, m;
		int i, j;
		scanf("%d%d", &n, &m);
		for (i = 1; i <= n; ++i)
			for (j = 1; j <= m; ++j)
				scanf("%d", &mark[i][j]);
		printf("%d\n", solve(n,m));
	}

    return 0;
}

#3

mark,观摩。。

#4

飞雪回答了，就不敢再回答了。呵呵

#5

学习中...

#6

飞雪的代码很强



我认为这是个排列组合问题   答案是C(m+n-2,m-1)。

#7

不知道啥叫动态规划。。。套用下飞雪的输入输出格式，我也贴个代码

#include <stdio.h>
int mark[31][31];
int sol[31][31];

int done(int n, int m)
{
    int i, j ;
    mark[0][1] = 1 ;
    sol[0][1] = 1 ;
    sol[1][0] = 0 ;
    for (i = 1 ; i <= n ; ++ i)
    {
        for (j = 1 ; j <= m ; ++ j)
        {
            sol[i][j] += mark[i - 1][j] * sol[i - 1][j] ;
            sol[i][j] += mark[i][j - 1] * sol[i][j - 1] ;
        }
    }

    return sol[n][m] ;
}

int main(void)
{
    int cnt;
    scanf("%d", &cnt);
    while (cnt--)
    {
        int n, m;
        int i, j;
        scanf("%d%d", &n, &m);
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= m; ++j)
                scanf("%d", &mark[i][j]);
//              printf("%d\n", solve(n,m));
                printf("%d\n", done(n, m)) ;
    }

    return 0;
}

#8

顺便说下我的乱七八糟思路。。。

 A    x01  x02  x03
 x10  x11  x12  x13
 x20  x21  x22  x23
 x30  x31  x32  B

x()表示到那个点的路径数，则总有x[i][j] = x[i - 1][j] + x[i][j - 1]。

#9

lz又没说不能后退不能向下，所以4*4的格子，正确答案是无数条路径，因为可以兜圈子~

joke~ 非降路径是典型题，算法分析书上一般都会讲

#10

呵呵 典型DP...