CCI 9.2 机器人移动路径

WBOY
풀어 주다: 2016-06-07 15:43:17
원래의
1100명이 탐색했습니다.

摄像有个机器人坐在X*Y网的左上角,只能想右、向下移动。机器人从(0,0)到(X,Y)有多少种走法? 进阶 假设有些点为“禁区”,机器人不能踏足。设计一种算法,找出一条路径,让机器人从左上角移动到右下角。 这道题跟LeetCode上的Unique Paths 和Unique Paths I

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

进阶

假设有些点为“禁区”,机器人不能踏足。设计一种算法,找出一条路径,让机器人从左上角移动到右下角。

这道题跟LeetCode上的Unique Paths 和Unique Paths II一样。

Unique Paths

A robot is located at the top-left corner of a m X n grid(marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of thr grid(marked 'Finish' in the diagram below).

How many possible unique paths are there?

CCI 9.2 机器人移动路径

NOTE: m and n will be at most 100.

Unique Paths II

Follow up for "Unique Paths".

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3*3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
로그인 후 복사
The total number of Unique paths is 2.

NOTE: m and n will be at most 100.

解法:

Unique Paths

public int uniquePaths(int m, int n) {
        //这里用了DP解法,因为这种解法可以最大程度避免整数越界问题
        int[][] memo = new int[m][n];
        for(int i=0; i<m i memo for j="1;" return>
<p>Unique Paths II</p>
<p>这里用了一维数组来代替二维数组</p>
<pre class="brush:php;toolbar:false">public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m == 0) return 0;
        int n = obstacleGrid[0].length;
        if(obstacleGrid[0][0] == 1) return 0;
        int[] table = new int[n];
        table[0] = 1;
        for(int i=0; i<m i for j="0;" if table else>0)
                    table[j] = table[j-1] + table[j];
            }
        }
        return table[n-1];
    }</m>
로그인 후 복사


관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!