文档章节

有个机器人坐在X*Y网格的左上角,只能向右、向下移动,机器人从(0,0)到(X,Y)有多少种走法

一贱书生
 一贱书生
发布于 2016/11/22 09:44
字数 2237
阅读 192
收藏 0
点赞 0
评论 0

/**
 * 功能:有个机器人坐在X*Y网格的左上角,只能向右、向下移动。机器人从(0,0)到(X,Y)有多少种走法。
 * 进阶:假设有些点为“禁区”,机器人不能踏足。找出一条路径,让机器人从左上角移动到右下角。

 */

 

解答:

排列组合问题:共有(X+Y)!/X!Y!

 

进阶问题有两种方法:

 

方法一:

[java] view plain copy

 

  1. //递归法  
  2. /** 
  3.  * 思路:自上而下 
  4.  * 从终点往回走,试着找出到其相邻点的路径。 
  5.  * @param x 
  6.  * @param y 
  7.  * @param path 
  8.  * @return 
  9.  */  
  10. public static boolean getPath(int x,int y,ArrayList<Point> path){  
  11.     Point p=new Point(x,y);  
  12.     path.add(p);  
  13.     if(x==0&&y==0)  
  14.         return true;//找到路径  
  15.       
  16.     boolean success=false;  
  17.     if(x>=1&&isFree(x-1,y))//向左走  
  18.         success=getPath(x-1,y, path);  
  19.     if(y>=1&&isFree(x,y-1))  
  20.         success=getPath(x,y-1,path);  
  21.       
  22.     if(!success)  
  23.         path.add(p);//错误路径  
  24.        
  25.     return success;  
  26.       
  27. }  


 

 

方法二:

 

[java] view plain copy

 

  1. <span style="white-space:pre">    </span>//动态规划  
  2.     /** 
  3.      * 思路:缓存先前访问过的点 
  4.      * @param x 
  5.      * @param y 
  6.      * @param path 
  7.      * @param cache 
  8.      * @return 
  9.      */  
  10.     public static boolean getPathDP(int x,int y,ArrayList<Point> path,HashMap<Point,Boolean> cache){  
  11.         Point p=new Point(x,y);  
  12.         if(x==0&y==0)  
  13.             return true;  
  14.           
  15.         path.add(p);  
  16.           
  17.         if(cache.containsKey(p))  
  18.             return cache.get(p);  
  19.           
  20.         boolean success=false;  
  21.         if(x>=1&&isFree(x-1,y))  
  22.             success=getPathDP(x-1, y, path, cache);  
  23.         if(y>=1&&isFree(x,y-1))  
  24.             success=getPathDP(x, y-1, path, cache);  
  25.           
  26.         if(!success)  
  27.             path.add(p);//错误路径的点  
  28.           
  29.         cache.put(p, success);//缓存结果  
  30.           
  31.         return success;  
  32.     }  
  33. }  
  34.   
  35. class Point{  
  36.     int x;  
  37.     int y;  
  38.     boolean isFree;  
  39.       
  40.     public Point(){}  
  41.     public Point(int x,int y){  
  42.         this.x=x;  
  43.         this.y=y;  
  44.     }  
  45. }

一、无障碍的网格

问题描述:

  有一个XxY的网格,一个机器人只能走格点且只能向右或向下走,要从左上角走到右下角。请设计一个算法,计算机器人有多少种走法。给定两个正整数int x,int y表示网格的大小,计算机器人的走法数目。

求解思路:

  对于本题,我们依然运用动态规划的思想。对于网格中的每一个格子,若该格子位于第一行,则只能由左边的格子到达;若格子位于第一列,只 能由上面的格子到达;网格中的其他格子可以由左边的格子到达,也可以由上面的格子到达。因此到达每一个格子的方法数都由左边的或者上面的格子所决定。我们 依次从网格的左上角遍历到右下角,则到达右下角格子的方法数便是最终的结果了。

代码实现:

 

[java] view plain copy

 

  1. import java.util.Scanner;  
  2. import java.util.Stack;  
  3. public class Main {  
  4.     public static void main(String[] args) {  
  5.         Scanner sc=new Scanner(System.in);  
  6.         int x=sc.nextInt();  
  7.         int y=sc.nextInt();  
  8.         if(x==0||y==0)   
  9.             System.out.println(0);  
  10.         else if(x==1||y==1)  
  11.             System.out.println(1);  
  12.         else{  
  13.             int [][]f=new int[x][y];  
  14.             for(int j=0;j<y;j++){  
  15.                 f[0][j]=1;  
  16.             }  
  17.             for(int i=0;i<x;i++){  
  18.                 f[i][0]=1;  
  19.             }  
  20.             for(int i=1;i<x;i++){  
  21.                 for(int j=1;j<y;j++){  
  22.                     f[i][j]=f[i][j-1]+f[i-1][j];  
  23.                 }  
  24.             }  
  25.             System.out.println(f[x-1][y-1]);  
  26.         }  
  27.     }  
  28. }  

二、有障碍的网格

 

问题描述:

 题目与上述类似,只是注意这次的网格中有些障碍点是不能走的,给定一个int[][]map表示网格图,若map[i][j]为0则说明该点不是障碍点,否则为障碍点。计算机器人从(0,0)走到(x - 1,y - 1)的走法数。

求解思路:

  求解思路也与上题类似,只是此时网格中有障碍点,我们可以这样考虑:

(1)当格子是障碍点时,机器人不能达到此格点,方法数为0;

(2)当格子不是障碍点时,则说明机器人向右走或向下走能到达此格子,因此到达此格子的方法数为到达其上方格子和左边格子的方法数之和。
代码实现:

 

[java] view plain copy

 

  1. public int countWays(int[][] map, int x, int y) {  
  2.         int step[][]=new int[x][y];  
  3.         if(map[0][0]==0) step[0][0]=1;  
  4.         else step[0][0]=0;  
  5.         for(int j=1;j<y;j++){  
  6.             if(map[0][j]==0)  
  7.                 step[0][j]=step[0][j-1];  
  8.             else  
  9.                 step[0][j]=0;  
  10.         }  
  11.         for(int i=1;i<x;i++){  
  12.             if(map[i][0]==0)  
  13.                 step[i][0]=step[i-1][0];  
  14.             else  
  15.                 step[i][0]=0;  
  16.         }  
  17.         for(int i=1;i<x;i++){  
  18.             for(int j=1;j<y;j++){  
  19.                 if(map[i][j]==0)  
  20.                     step[i][j]=step[i][j-1]+step[i-1][j];  
  21.                 else  
  22.                     step[i][j]=0;  
  23.             }  
  24.         }  
  25.         return step[x-1][y-1];  
  26.     } 
  27.  

在一个N*N矩阵的左上角坐着一个机器人,它只能向右运动或向下运动。那么, 机器人运动到右下角一共有多少种可能的路径?

进一步地,

如果对于其中的一些格子,机器人是不能踏上去的。设计一种算法来获得所有可能的路径。

解答

为了一般化这个问题,我们假设这个矩阵是m*n的,左上角的格子是(1, 1), 右下角的坐标是(m, n)。

解法一

这个题目可以递归来解,如何递归呢?首先,我们需要一个递推公式, 对于矩阵中的格子(i, j),假设从(1, 1)到它的路径数量为path(i, j), 那么,有:

path(i, j) = path(i-1, j) + path(i, j-1)

很好理解,因为机器人只能向右或向下运动,因此它只能是从(i-1, j)或(i, j-1) 运动到(i, j)的,所以路径数量也就是到达这两个格子的路径数量之和。然后, 我们需要一个初始条件,也就是递归终止条件,是什么呢?可以发现, 当机器人在第一行时,不论它在第一行哪个位置,从(1, 1)到达那个位置都只有一条路径, 那就是一路向右;同理,当机器人在第一列时,也只有一条路径到达它所在位置。 有了初始条件和递推公式,我们就可以写代码了,如下:

ll path(ll m, ll n){
    if(m == 1 || n == 1) return 1;
    else return path(m-1, n) + path(m, n-1);
}

ll是数据类型long long。

解法二

如果用纯数学的方法来解这道题目,大概也就是个高中排列组合简单题吧。 机器人从(1, 1)走到(m, n)一定要向下走m-1次,向右走n-1次,不管这过程中是怎么走的。 因此,一共可能的路径数量就是从总的步数(m-1+n-1)里取出(m-1)步,作为向下走的步子, 剩余的(n-1)步作为向右走的步子。

C(m-1+n-1, m-1)=(m-1+n-1)! / ( (m-1)! * (n-1)! )

代码如下:

ll fact(ll n){
    if(n == 0) return 1;
    else return n*fact(n-1);
}
ll path1(ll m, ll n){
    return fact(m-1+n-1)/(fact(m-1)*fact(n-1));
}

对于第二问,如果有一些格子,机器人是不能踏上去的(比如说放了地雷XD), 那么,我们如何输出它所有可能的路径呢?

让我们先来考虑简单一点的问题,如果我们只要输出它其中一条可行的路径即可, 那么我们可以从终点(m, n)开始回溯,遇到可走的格子就入栈, 如果没有格子能到达当前格子,当前格子则出栈。最后到达(1, 1)时, 栈中正好保存了一条可行路径。代码如下:

bool get_path(int m, int n){
    point p; p.x=n; p.y=m;
    sp.push(p);
    if(n==1 && m==1) return true;
    bool suc = false;
    if(m>1 && g[m-1][n])
        suc = get_path(m-1, n);
    if(!suc && n>1 && g[m][n-1])
        suc = get_path(m, n-1);
    if(!suc) sp.pop();
    return suc;
}

其中二维数组g表示的是M*N的矩阵,元素为1表示该位置可以走,为0表示该位置不可走。 这个只能得到其中一条可行路径,但题目是要求我们找到所有可行路径,并输出。 这样的话,又该怎么办呢?我们从(1, 1)开始,如果某个格子可以走, 我们就将它保存到路径数组中;如果不能走,则回溯到上一个格子, 继续选择向右或者向下走。当机器人走到右下角的格子(M, N)时,即可输出一条路径。 然后程序会退出递归,回到上一个格子,找寻下一条可行路径。代码如下:

void print_paths(int m, int n, int M, int N, int len){
    if(g[m][n] == 0) return;
    point p; p.x=n; p.y=m;
    vp[len++] = p;
    if(m == M && n == N){
        for(int i=0; i<len; ++i)
            cout<<"("<<vp[i].y<<", "<<vp[i].x<<")"<<" ";
        cout<<endl;
    }
    else{
        print_paths(m, n+1, M, N, len);
        print_paths(m+1, n, M, N, len);
    }
}

程序使用的输入样例8.2.in如下:

3 4
1 1 1 0
0 1 1 1
1 1 1 1

输出路径如下:

one of the paths:
(1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) 
all paths:
(1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) 
(1, 1) (1, 2) (1, 3) (2, 3) (3, 3) (3, 4) 
(1, 1) (1, 2) (2, 2) (2, 3) (2, 4) (3, 4) 
(1, 1) (1, 2) (2, 2) (2, 3) (3, 3) (3, 4) 
(1, 1) (1, 2) (2, 2) (3, 2) (3, 3) (3, 4)

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
scrollTo、scrollBy、getScrollX、getScrollY这4个方法的含义

源码下载地址结合程序和图作出说明:1、关于自定义视图继承ViewGroup中的onMeasure和onLayout是怎么实现我就不多说了,此博文主要是说明scrollTo、scrollBy、getScrollX、getScrollY这4个方法...

茶码古道 ⋅ 2014/05/28 ⋅ 0

scrollTo、scrollBy、getScrollX、getScrollY这4个方法的含义

推荐一款app应用——"印度爱经",木蚂蚁下载点击打开链接 源码下载地址 结合程序和图作出说明: 1、关于自定义视图继承ViewGroup中的onMeasure和onLayout是怎么实现我就不多说了,此博文主要...

Jonson ⋅ 2014/05/15 ⋅ 1

KUKA机器人的空间变换问题

在kuka机器人系统的FRAME和POS数据结构包含六个参数:{X ,Y,Z,A,B,C}。这些参数正好对应角度坐标系表示中的六个参数, X,Y,Z,alpha,beta,gama,且alpha=A,beta=B,gama=C。 假设在机器人系统中,...

JayH ⋅ 2015/02/26 ⋅ 0

给二维数组,存(0,0) -> (m, n)个点,就是一个m * n 的网格, 从左上角(0...

给二维数组,存(0,0) -> (m, n)个点,就是一个m * n 的网格, 从左上角(0,0)走到右下角(m,n)只能向右走或者向下走,有多 少种走法,打印每一种走法。 /===========================...

dapengking ⋅ 2013/03/25 ⋅ 0

getRawX、getRawY与getX、getY以及getScrollX、getScrollY

图解MotionEvent中getRawX、getRawY与getX、getY以及View中的getScrollX、getScrollY 1.getRawX、getRawY与getX、getY的区别 在编写android的自定义控件,或者判断用户手势操作时,往往需要使...

aspirs ⋅ 2016/02/01 ⋅ 0

Android 图解Canvas drawText文字居中的那些事

封面 GitHub传送门 1.写在前面 在实现自定义控件的过程中,常常会有绘制居中文字的需求,于是在网上搜了一些相关的博客,总是看的一脸懵逼,就想着自己分析一下,在此记录下来,希望对大家能...

容华谢后 ⋅ 2017/12/29 ⋅ 0

Android View中滚动相关

方法 scrollTo: (内容的左上角)达到某个地点 scrollBy: 根据当前位置,再移动多少 属性: mScrollX, 以下是文档解释 The offset, in pixels, by which the content of this view is scrolled...

okker ⋅ 2013/12/30 ⋅ 2

51nod 1119 机器人走方格 V2

1119 机器人走方格 V2 难度:2级算法题 收藏 关注 M * N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10^9 + 7的结果。 ...

Fire_to_cheat_ ⋅ 2017/12/31 ⋅ 0

关于常见矩阵路径计算问题(iOS版本)

关于常见矩阵路径计算问题(iOS版本) 729dcafcfc039245b8f04f668c94a4c27c1e25e2.jpg 常见类型介绍: /*●问题描述: 给出一个矩阵,其中0表示通路,1表示墙壁,这样就形成了一个迷宫,要求编...

一路向北客 ⋅ 2017/12/01 ⋅ 0

51Nod 1119 机器人走方格 V2

M * N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10^9 + 7的结果。 Input 第1行,2个数M,N,中间用空格隔开。(2 <= ...

Akatsuki__Itachi ⋅ 2017/12/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

SpringCloud 微服务 (六) 服务通信 RestTemplate

壹 通信的方式主要有两种,Http 和 RPC SpringCloud使用的是Http方式通信, Dubbo的通信方式是RPC 记录学习SpringCloud的restful方式: RestTemplate (本篇)、Feign 贰 RestTemplate 类似 Http...

___大侠 ⋅ 14分钟前 ⋅ 0

React创建组件的三种方式

1.无状态函数式组建 无状态函数式组件,也就是你无法使用State,也无法使用组件的生命周期方法,这就决定了函数组件都是展示性组件,接收Props,渲染DOM,而不关注其他逻辑。 无状态函数式组...

kimyeongnam ⋅ 21分钟前 ⋅ 0

react 判断实例类型

今天在写组件的时候想通过判断内部子元素不同而在父元素上应用不同的class,于是首先要解决的就是如何判断子元素的类型。 这里附上一个讲的很全面的文章: https://www.cnblogs.com/onepixel...

球球 ⋅ 27分钟前 ⋅ 0

Centos7备份数据到百度网盘

一、关于 有时候我们需要进行数据备份,如果能自动将数据备份到百度网盘,那将会非常方便。百度网盘有较大的存储空间,而且不怕数据丢失,安全可靠。下面简单的总结一下如何使用 bypy 实现百...

zctzl ⋅ 41分钟前 ⋅ 0

开启远程SSH

SSH默认没有开启账号密码登陆,需要再配置表中修改: vim /etc/ssh/sshd_configPermitRootLogin yes #是否可以使用root账户登陆PasswordAuthentication yes #是都开启密码登陆ser...

Kefy ⋅ 44分钟前 ⋅ 0

Zookeeper3.4.11+Hadoop2.7.6+Hbase2.0.0搭建分布式集群

有段时间没更新博客了,趁着最近有点时间,来完成之前关于集群部署方面的知识。今天主要讲一讲Zookeeper+Hadoop+Hbase分布式集群的搭建,在我前几篇的集群搭建的博客中已经分别讲过了Zookeep...

海岸线的曙光 ⋅ 52分钟前 ⋅ 0

js保留两位小数方法总结

本文是小编针对js保留两位小数这个大家经常遇到的经典问题整理了在各种情况下的函数写法以及遇到问题的分析,以下是全部内容: 一、我们首先从经典的“四舍五入”算法讲起 1、四舍五入的情况...

孟飞阳 ⋅ 今天 ⋅ 0

python log

python log 处理方式 log_demo.py: 日志代码。 #! /usr/bin/env python# -*- coding: utf-8 -*-# __author__ = "Q1mi""""logging配置"""import osimport logging.config# 定义三种......

inidcard ⋅ 今天 ⋅ 0

mysql 中的信息数据库以及 shell 查询 sql

Information_schema 是 MySQL 自带的信息数据库,里面的“表”保存着服务器当前的实时信息。它提供了访问数据库元数据的方式。 什么是元数据呢?元数据是关于数据的数据,如数据库名或表名,...

blackfoxya ⋅ 今天 ⋅ 0

maven配置阿里云镜像享受飞的感觉

1.在maven目录下的conf/setting.xml中找到mirrors添加如下内容,对所有使用改maven打包的项目生效。 <mirror> <id>alimaven</id> <name>aliyun maven</name> <url>http://maven.al......

kalnkaya ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部