首页 > 试题广场 >

机器人走方格II

[编程题]机器人走方格II

热度指数：19330 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int[][] map(C++ 中为vector >)网格图，若map[i][j]为1则该点不是障碍点，否则为障碍点。另外给定int x,int y，表示网格的大小。现有一个机器人要从网格左上角走到右下角，只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出，并保证x和y均小于等于50。

算法知识视频讲解

Java

未命名丶

import java.util.*;

public class Robot {
public int countWays(int[][] map, int x, int y) {
// write code here
int[][] mark = new int[x][y];
if(map[0][0] != 1) return 0;

mark[0][0] = 1;
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (map[i][j] == 1) {
if(i - 1 >= 0){
mark[i][j] = (mark[i][j] + mark[i-1][j]) % 1000000007;
}
if(j - 1 >= 0){
mark[i][j] = (mark[i][j] + mark[i][j-1]) % 1000000007;
}
}
}
}
return mark[x-1][y-1];
}
}

发表于 2020-11-02 15:35:26 回复(0)

Java

年深坑

本题考点是动态规划。递归进行了大量的重复无用计算。用递归或者回溯肯定是会超时的。

还有一个小细节就是有可能[0,0]和[x-1,y-1]本身就是障碍点，是不可到达的。

public class 机器人走方格 {

    public static int countWays(int[][] map, int x, int y) {
// write code here
        if(map[0][0]==0 || map[x-1][y-1]==0)    return 0;
long res[][]=new long[x][y],    mod=1000000007;
res[x-1][y-1]=1;
for(int j=y-2;j>=0;j--)
        if(map[x-1][j+1]==1)    res[x-1][j]=res[x-1][j+1];
for(int i=x-2;i>=0;i--)
    if(map[i+1][y-1]==1)    res[i][y-1]=res[i+1][y-1];
for(int i=x-2;i>=0;i--) {
    for(int j=y-2;j>=0;j--) {
        if(map[i+1][j]==1)    res[i][j]+=res[i+1][j];
        if(map[i][j+1]==1)    res[i][j]+=res[i][j+1];
    }
}
return (int) (res[0][0]%mod);
}

发表于 2018-06-13 13:52:59 回复(0)

Java

哎呦呦呦呦丁

思路：动态规划递归式为dp[i][j]=dp[i-1][j]+dp[i][j-1]    dp[i][j]表示从i到j有多少种走法

import java.util.*;

public class Robot {
    public int countWays(int[][] map, int x, int y) {
        
        int[][] dp=new int[x][y];
        
        for(int k=0;k<y;k++){//为第一行赋初值
            if(map[0][k]==1){
                dp[0][k]=1;//从起点开始向右走就只有一种走法
            } 
            else {
                dp[0][k]=0;//如果有障碍，则就无法到达，所以dp[0][k]=0,该行后边的自然也都无法到达
                  break;
        		} 
        }
        for(int k=0;k<x;k++){//为第一列赋初值
            if(map[k][0]!=1) {
                dp[k][0]=0;
                break;
                  }
            else  dp[k][0]=1;
        }
            
        for(int i=1;i<x;i++){
            for(int j=1;j<y;j++){
                if(map[i][j]!=1) dp[i][j]=0;//要到达的点是障碍点则说明不可达。所以dp[i][j]=0
                else
                    dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
            }
        }
        return dp[x-1][y-1];
    }
}

编辑于 2017-05-22 11:25:13 回复(2)