首页 > 试题广场 >

在如下8*6的矩阵中，请计算从A移动到B一共有多少种走法，要

[单选题]

在如下8*6的矩阵中，请计算从A移动到B一共有多少种走法，要求每次只能向上或向右移动一格，并且不能通过P（）

B

P

A 

  • 702
  • 626
  • 456
  • 680
  • 568
  • 492
查看正确选项
添加回答
牛客426401459号头像 牛客426401459号 
public class Demo06 {
    public static void main(String[] args) {
        int i =Solution(8,6);//A到B全部走法792
        int j =Solution(5,3);//A到P的全部走法
        int k = Solution(4,4);//P到B的走法
        System.out.println(i-j*k);
    }
    public  static  int Solution( int m,int n){

        if(m<=1||n<=1){
            return 1;
        }if (m==2 && n ==2){
            return 2;
        }else {
            return Solution(m, n-1)+Solution(m-1,n);
        }
    }
}
简单的递归调用。
发表于 2021-03-27 11:16:26 回复(0)
慢慢哒头像 慢慢哒
8*6的矩阵，从左下角A到右上角B，一共需要走12步，其中5步向上，7步向右，因此总的走法一共有C(12,5)=792种，但题目规定不能经过P，因此需要减去经过P点的走法。 经过P的路径分为两部分，从A到P，从P到B。 同理，从A到P的走法：C(6,2)=15； 同理，从P到B的走法：C(6,3)=20； 因此从A到B经过P点的走法有15*20=300种， 所以从A到B不经过P点的走法有792-300=492种。 A(m,n)=n*(n-1)*...*(n-m+1) C(m,n)=A(m,n)%A(m,m)=n*(n-1)*(n-m+1)%m*(m-1)*1
发表于 2017-03-05 17:57:42 回复(2)
love_truth头像 love_truth
据说这叫动态规划....
发表于 2019-05-19 17:15:24 回复(3)
Croyal头像 Croyal
F
解题思路：dfs计算从A到B的总方案数，P点标记为不可走的。 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

int g[6][8];
bool vis[6][8];
int ans;
int dir[2][2]={{-1,0},{0,1}};

void dfs(int x,int y)
{
    if(x==0&&y==7){
        ans++;
        return;
    }
    vis[x][y]=true;
    for(int i=0;i<2;i++){
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(xx>=0&&xx<6&&yy>=0&&yy<8&&!vis[xx][yy]&&!g[xx][yy]){
            dfs(xx,yy);
        }
    }
    vis[x][y]=false;
}

int main()
{
    memset(g,0,sizeof(g));
    memset(vis,false,sizeof(vis));
    g[3][4]=1;
    ans=0;
    dfs(5,0);
    cout<<ans<<endl;
    return 0;
}


发表于 2017-01-23 13:37:01 回复(3)
时间的诗头像 时间的诗
排列组合，从12步中选5中纵向的，则横向的也就定了；A到P，P到B是一条路，相乘
发表于 2017-08-19 11:06:01 回复(0)
stacysong头像 stacysong

排列组合

发表于 2019-04-27 13:59:41 回复(0)
路人甲自由头像 路人甲自由 
deffindway(x,y):if(x==0)or(y==0):return1 else:returnfindway(x-1,y)+findway(x,y-1)print(findway(7,5)-(findway(4,2)*findway(3,3)))
发表于 2019-03-08 15:04:46 回复(0)
牛客525175867号头像 牛客525175867号
问个特蠢的问题792怎么算出来的啊，我没懂(´ー`)
发表于 2019-08-10 13:38:29 回复(4)
馮成浩头像 馮成浩 
def findway(x,y): if (x==0) or (y==0): return 1  else: return findway(x-1,y)+findway(x,y-1) print(findway(7,5)-(findway(4,2)*findway(3,3)))

发表于 2018-02-03 08:51:49 回复(0)
菜牛1号头像 菜牛1号
题目说每次只能向上或者向右移动一格，也就是说连续向上移动或者向右移动是不行的，答案C(12,5)-C(6,2)*C(6,3)=492是不是有问题？？
发表于 2017-07-31 15:47:22 回复(5)
提交观点

问题信息

数学运算
来自：凤凰网2017秋招研发...
上传者：牛100
难度：
10条回答 5044浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号