给定一个int[][] map(C++ 中为vector >)网格图，若map[i][j]为1则该点不是障碍点，否则为障碍点。另外给定int x,int y，表示网格的大小。现有一个机器人要从网格左上角走到右下角，只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出，并保证x和y均小于等于50。
[编程题]机器人走方格II
貌似前两天看到还有公司在考这个的，动归打表
class Robot {
public:
int countWays(vector<vector<int> > map, int x, int y) {
vector<vector<int> > dp(x,vector<int>(y,0));
for(int i = 0; i < x; i ++){
for(int j = 0; j < y; j ++){
if(map[i][j] != 1) continue;
if(i == 0 && j == 0) dp[0][0] = 1;
else if(i != 0 && j == 0) dp[i][0] = dp[i-1][0] ;
else if(i == 0 && j != 0) dp[0][j] = dp[0][j-1] ;
else{
dp[i][j] = (dp[i][j-1] + dp[i-1][j])%1000000007;
}
}
}
return dp[x-1][y-1];
}
};
发表于 2015-09-14 14:32:34
回复(8)
经典动态规划，
建立规划矩阵f
遍历所有情况，生成f举证就可以，
对map的处理：不能走这个点，说明这个点的可能路径走法==0，经过不能走的点写成0就可以了
总结一下就是：
- 不能走，就是方法数==0
- 起点，1种走法
- 上边沿：只能从左边来
- 左边沿：只能从上边来
- 其他点：左边+上边
int countWays(vector<vector<int> > map, int x, int y) {
vector<vector<int> > f(x,vector<int>(y,0));
for(int i=0;i<x;i++)
for(int j=0;j<y;j++)
{
if(map[i][j] != 1)f[i][j] = 0; // 不能走，就是方法数==0
else if(i==0 && j==0)f[i][j] = 1; // 起点，1种走法
else if(i==0 && j!=0)f[i][j] = f[i][j-1]; // 上边沿：只能从左边来
else if(i!=0 && j==0)f[i][j] = f[i-1][j]; // 左边沿：只能从上边来
else f[i][j] = (f[i-1][j]+f[i][j-1]) % 1000000007; // 其他点：左边+上边
}
return f[x-1][y-1];
}
发表于 2016-09-01 22:54:46
回复(0)
import java.util.*;
/*
看到题目说防止溢出，然后我就不敢用递归了，那就迭代？一步步做，试试看吧
*/
public class Robot {
public int countWays(int[][] map, int x, int y) {
if(x==0||y==0) return 1;
int array[][] =new int[x][y];
if(map[0][0]==0||map[x-1][y-1]==0) return 0;//题目真的无聊，还把0.0点设成障碍物了。。
array[0][0]=1;//开始在这里没有考虑清楚，一旦array[i][0]中有某个障碍物，那其后面均应该是0，而不是1
for(int i=1;i<x;i++){//这里第一行和第一列的值要和后面的二维遍历分开设定，不然在二维数组的遍历中会存在数组越界
if(map[i][0]==1) array[i][0]=array[i-1][0];//也可以用break的方式
else array[i][0]=0;
}
for(int j=1;j<y;j++){
if(map[0][j]==1) array[0][j]=array[0][j-1];
else array[0][j]=0;
}
for(int i=1;i<x;i++){
for(int j=1;j<y;j++){
array[i][j] =((map[i-1][j]==0?0:array[i-1][j])+(map[i][j-1]==0?0:array[i][j-1]))%1000000007;
}
}
return array[x-1][y-1];
}
}
运行时间：57ms
占用内存：9824k
发表于 2017-06-28 16:24:34
回复(0)
优化空间为一维。
class Robot {
public:
int countWays(vector<vector<int> > map, int x, int y) {
// write code here
vector<int> dp(y);
const int Mod = 1000000007;
dp[0] = 1;
for(int i = 0; i < x; i++) {
for(int j = 0; j < y; j++) {
if(map[i][j] != 1)
dp[j] = 0;
else if(j > 0)
dp[j] = dp[j] % Mod + dp[j - 1] % Mod;
}
}
return dp[n - 1] % Mod;
}
};
发表于 2017-04-14 23:17:43
回复(0)
public int countWays(int[][] map, int x, int y) {
// write code here
/*
* 1.判断右下角的点以及起点自身是否为障碍点，若是返回0；
* 2.若右下角的点非障碍点，判断上面和左边是否为障碍点
* 1.若全都为障碍点，返回0
* 2.若一个为障碍点，一个不是，则到该点的路径数等于上一个点的路径数（这是递归的思路）
* 第2部分可以不用递归，而用循环：
* dp[i-1][j-1]表示从(0,0)到(i,j)的方法数，如果(i,j)非1，则为障碍点，对应dp[i-1][j-1]为0
* 其余情况与一般dp相同
*/
if(map == null || map.length != x || map[0].length != y){
return 0;
}
if(map[x-1][y-1] != 1 || map[0][0] != 1){//最后一个点为障碍点
return 0;
}
int dp[][] = new int[x][y];
dp[0][0] = 1;
for(int i = 1; i < x; i++){
if(map[i][0] != 1){
dp[i][0] = 0;
}else{
dp[i][0] = dp[i-1][0];
}
}
for(int i = 1; i < y; i++){
if(map[0][i] != 1){
dp[0][i] = 0;
}else{
dp[0][i] = dp[0][i-1];
}
}
for(int i = 1; i < x; i++){
for(int j = 1; j < y; j++){
if(map[i][j] != 1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i-1][j]%1000000007 + dp[i][j-1]%1000000007;
}
}
}
return (dp[x-1][y-1]%1000000007);
}
发表于 2016-04-27 18:06:33
回复(6)
public class Rebot {
public int countWays(int[][] map, int x, int y) {
return countdym(map, x, y);
}
public int countdym(int[][] map, int x, int y) {
int[][] target = new int[x][y];
boolean flag = true;
for (int i = 0; i < y; i++) {
if (map[0][i] == 1 && flag) {
target[0][i] = 1;
} else {
flag = false;
target[0][i] = 0;
}
}
flag = true;
for (int i = 0; i < x; i++) {
if (map[i][0] == 1 && flag) {
target[i][0] = 1;
} else {
flag = false;
target[i][0] = 0;
}
}
for (int i = 1; i < x; i++) {
for (int j = 1; j < y; j++) {
if (map[i][j] == 1) {
target[i][j] = target[i - 1][j] + target[i][j - 1];
} else {
target[i][j] = 0;
}
}
}
return target[x - 1][y - 1];
}
}
发表于 2015-10-05 11:56:50
回复(4)
int countWays(vector<vector<int> > map, int x, int y) {
vector<vector<int>>dp(x+1,vector<int>(y+1,0));
const int mod = 1000000007;
for(int i=0;i<x;++i)
for(int j=0;j<y;++j){
if(i==0&&j==0&&map[i][j]!=1)return 0;
else if(i==0&&j==0)dp[i+1][j+1] = 1;
else if(map[i][j] != 1)dp[i+1][j+1] = 0;
else dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1];
dp[i+1][j+1] %= mod;
}
return dp[x][y];
}
发表于 2019-09-01 19:32:44
回复(0)
class Robot {
public:
int countWays(vector<vector<int> > map, int x, int y) {
// write code here
if(!map[0][0]) return 0;
int dp[x][y];
for (int i = 0; i < x; ++i)
for (int j = 0; j < y; ++j) {
dp[i][j] = 0;
}
if(map[0][1]) dp[0][1] = 1;
if(map[1][0]) dp[1][0] = 1;
for (int i = 0; i < x; ++i) {
for (int j = 0; j < y; ++j) {
if(i - 1 >= 0 && map[i-1][j] && map[i][j]) dp[i][j] += dp[i-1][j];
if(j - 1 >= 0 && map[i][j-1] && map[i][j]) dp[i][j] += dp[i][j-1];
}
}
return dp[x-1][y-1];
}
};
发表于 2019-06-11 16:13:05
回复(0)
# -*- coding:utf-8 -*-
class Robot:
def countWays(self, m, x, y):
# write code here
tmparray=[[0]*(y+1) for _ in range(x+1)]
for i in range(1,x+1):
for j in range(1,y+1):
if m[i-1][j-1]!=0:
tmparray[i][j]=tmparray[i-1][j]+tmparray[i][j-1] if ((j!=1) or (i!=1)) else 1
return tmparray[x][y]
class Robot:
def countWays(self, m, x, y):
# write code here
tmparray=[[0]*(y+1) for _ in range(x+1)]
for i in range(1,x+1):
for j in range(1,y+1):
if m[i-1][j-1]!=0:
tmparray[i][j]=tmparray[i-1][j]+tmparray[i][j-1] if ((j!=1) or (i!=1)) else 1
return tmparray[x][y]
发表于 2019-05-29 12:16:21
回复(0)
二维DP
class Robot {
public:
int countWays(vector<vector<int> > map, int x, int y) {
int F[55][55]{0, 1};
for (int i=1; i<=x; ++i) {
for (int j=1; j<=y; ++j) {
F[i][j] = (map[i-1][j-1] == 1) * (F[i-1][j] + F[i][j-1]) % 1000000007;
}
}
return F[x][y];
}
}; 利用滚动数组优化：
class Robot {
public:
int countWays(vector<vector<int> > map, int x, int y) {
int F[55]{0, 1};
for (int i=1; i<=x; ++i) {
for (int j=1; j<=y; ++j) {
F[j] = (map[i-1][j-1] == 1) * (F[j] + F[j-1]) % 1000000007;
}
}
return F[y];
}
};
编辑于 2018-12-29 15:26:33
回复(0)
import java.util.*;
public class Robot {
public int countWays(int[][] map, int x, int y) {
// write code here
if(map == null || map.length == 0 || map[0].length == 0){
return 0;
}
if(map[x-1][y-1] != 1 || map[0][0] != 1){//最后一个点为障碍点
return 0;
}
int[][] dp = new int[x][y];
dp[0][0] = 1;
for(int i = 1 ; i < x ; i++){
if(map[i][0] == 1){
dp[i][0] = dp[i - 1][0];
}else{
dp[i][0] = 0;
}
}
for(int j = 1 ; j < y ; j++){
if(map[0][j] == 1){
dp[0][j] = dp[0][j - 1];
}else{
dp[0][j] = 0;
}
}
for(int i = 1 ; i < x ; i++){
for(int j = 1 ; j < y ;j++){
if(map[i][j] == 1){
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
}else{
dp[i][j] = 0;
}
}
}
return dp[x - 1][y - 1];
}
}
发表于 2018-09-08 10:50:40
回复(0)
dp问题：
public int countWaysTwo(int[][] map,int x,int y){
int[][] dp = new int[x][y];
for (int i = 0 ; i < x ;i++) {
for (int j = 0 ; j < y ; j++) {
if (map[i][j] != 1){
continue;
}
if (i == 0 && j == 0) {
dp[i][j] = 1;
}else if (i == 0 && j != 0) {
dp[i][j] = dp[i][j-1];
}else if (i != 0 && j == 0) {
dp[i][j] = dp[i-1][j];
}else {
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
}
}
}
return dp[x-1][y-1];
}
回溯法（超时了）
public int countWays(int[][] map, int x, int y) {
return core(map, x, y, 0, 0);
}
private int core(int[][] map, int row, int col, int currentX, int currentY) {
int ret = 0;
if (map[currentX][currentY] != 1){
return 0;
}
if ((currentX == (row - 1)) && (currentY == (col - 1)) ) {
return 1;
}
if (currentX + 1 < row) {
ret += core(map, row, col, currentX + 1, currentY);
ret = ret % 1000000007;
}
if (currentY + 1 < col) {
ret += core(map, row, col, currentX, currentY + 1);
ret = ret % 1000000007;
}
return ret;
}
发表于 2018-03-30 17:21:05
回复(0)
class Robot {
public:
int countWays(vector<vector<int> > map, int x, int y) {
// write code here
if (map[0][0] == 1) {
for (auto i = 0; i < x; ++i) {
for (auto j = 0; j < y; ++j) {
if ((i <= 1 && j == 0) || (j <= 1 && i == 0)) {
if (map[i][j] == 1) {}
else { map[i][j] = 0; }
}
else if (i == 0) {
if (map[i][j] == 1) { map[i][j] = map[i][j - 1]; }
else { map[i][j] = 0; }
}
else if (j == 0) {
if (map[i][j] == 1) { map[i][j] = map[i - 1][j]; }
else { map[i][j] = 0; }
}
else {
if (map[i][j] == 1) { map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1000000007; }
else { map[i][j] = 0; }
}
}
}
return map[x - 1][y - 1];
}
else { return 0; }
}
};
public:
int countWays(vector<vector<int> > map, int x, int y) {
// write code here
if (map[0][0] == 1) {
for (auto i = 0; i < x; ++i) {
for (auto j = 0; j < y; ++j) {
if ((i <= 1 && j == 0) || (j <= 1 && i == 0)) {
if (map[i][j] == 1) {}
else { map[i][j] = 0; }
}
else if (i == 0) {
if (map[i][j] == 1) { map[i][j] = map[i][j - 1]; }
else { map[i][j] = 0; }
}
else if (j == 0) {
if (map[i][j] == 1) { map[i][j] = map[i - 1][j]; }
else { map[i][j] = 0; }
}
else {
if (map[i][j] == 1) { map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1000000007; }
else { map[i][j] = 0; }
}
}
}
return map[x - 1][y - 1];
}
else { return 0; }
}
};
发表于 2017-12-14 14:36:26
回复(0)
python solution
# -*- coding:utf-8 -*-
class Robot:
def countWays(self, m, x, y):
if m[-1][-1]==0:return 0
for i in range(x-1,-1,-1):
if m[i][-1]==1:
m[i][-1]==1
else:
for j in range(i,-1,-1):
m[j][-1]=0
break
for i in range(y-2,-1,-1):
if m[-1][i]==1:
m[-1][i]=1
else:
for j in range(i,-1,-1):
m[-1][j]=0
for i in range(x-2,-1,-1):
for j in range(y-2,-1,-1):
if m[i][j]==1:
m[i][j]=m[i+1][j]+m[i][j+1]
else:
m[i][j]=0
return m[0][0]
发表于 2017-10-31 18:02:51
回复(0)
import java.util.*;
public class Robot {
public int countWays(int[][] map, int x, int y) {
// write code here
int[][] dp = new int[x][y];
for(int i = 0; i < x; i++){
if(map[i][0] == 1){
dp[i][0] = 1;
}else{
break;
}
}
for(int i = 0; i < y; i++){
if(map[0][i] == 1){
dp[0][i] = 1;
}else{
break;
}
}
for(int i = 1; i < x; i++){
for(int j = 1; j < y; j++){
if(map[i][j] == 1){
if(map[i - 1][j] == 1 && map[i][j - 1] == 1){
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) %1000000007;
}else{
if(map[i - 1][j] == 1){
dp[i][j] = dp[i - 1][j] % 1000000007;
}else if(map[i][j - 1] == 1){
dp[i][j] = dp[i][j - 1] % 1000000007;
}else{
dp[i][j] = 0;
}
}
}else{
dp[i][j] = 0;
}
}
}
return dp[x - 1][y - 1];
}
}
发表于 2017-08-28 11:11:45
回复(0)
/*
*方法一非递归直接开数组（费空间）
*方法二滚动数组（省空间）
*/
import java.util.*;
public class Robot {
public int countWays(int[][] map, int x, int y) {
// write code here
int out[][]=new int[x][y];
for(int i=0;i<x;i++){
if(map[i][0]==1)
out[i][0]+=1;
else
break;
}
for(int i=0;i<y;i++){
if(map[0][i]==1)
out[0][i]+=1;
else
break;
}
for(int i=1;i<x;i++){
for(int j=1;j<y;j++){
if(i>0 && map[i-1][j]==1){
out[i][j]+=out[i-1][j]%1000000007;
}
if(j>0 && map[i][j-1]==1){
out[i][j]+=out[i][j-1]%1000000007;
}
if(map[i][j]!=1){
out[i][j]=0;
}
}
}
return out[x-1][y-1];
}
}
import java.util.*;
public class Robot {
public int countWays(int[][] map, int x, int y) {
// write code here
int out[]=new int[y+1];
out[0]=0;
for(int i=1;i<y+1;i++){
if(map[0][i-1]==1)
out[i]+=1;
else
break;
}
for(int i=1;i<x;i++){
for(int j=1;j<y+1;j++){
if(map[i][j-1]!=1){
out[j]=0;
}else{
out[j]+=out[j-1]%1000000007;
}
}
}
return out[y];
}
}
编辑于 2017-06-22 18:31:04
回复(0)
思路：动态规划递归式为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)
class Robot {
public:
int countWays(vector<vector<int> > map, int x, int y) {
// write code here
if (map[0][0] != 1)
return 0;
vector<vector<int> > dp(x, vector<int>(y, 0));
for (int i = 0; i < x; ++i){
if (map[i][0] != 1)
break; // 如果i行0列为障碍点，则下面就走不了. 为0
dp[i][0] = 1;
}
for (int j = 0; j < y; ++j){
if (map[0][j] != 1)
break; // 如果0行j列为障碍点，则右面就走不了，为0
dp[0][j] = 1;
}
for (int i = 1; i < x; ++i){
for (int j = 1; j < y; ++j){
if (map[i][j] != 1)
dp[i][j] = 0;
else
dp[i][j] = dp[i - 1][j]%1000000007 + dp[i][j - 1]%1000000007;
}
}
return dp[x - 1][y - 1]%1000000007;
}
};
编辑于 2017-04-26 17:01:54
回复(0)
#Python版
#需判断一下这一步能不能走
# -*- coding:utf-8 -*-
class Robot:
def countWays(self, m, x, y):
# write code here
if m is None:
return -1
lenRows = len(m)
lenCols = len(m[0])
if x<=0 or x>lenRows or y <=0 or y >lenCols:
return 0
res = []
for i in range(x):
tmp = []
for j in range(y):
tmp.append(0)
res.append(tmp)
if m[0][0] != 1:
return 0
res[0][0] = 1
for i in range(1,x):
if m[i][0] ==1:
res[i][0] = res[i-1][0]
else:
res[i][0] = 0
for i in range(1,y):
if m[0][i] == 1:
res[0][i] = res[0][i-1]
else:
res[0][i] = 0
for i in range(1,x):
for j in range(1,y):
if m[i][j] ==1:
if res[i-1][j] != 0 and res[i][j-1] != 0:
res[i][j] = (res[i-1][j]%1000000007+res[i][j-1]%1000000007)%1000000007
if res[i-1][j] == 0 and res[i][j - 1] != 0:
res[i][j] = res[i][j - 1]%1000000007
if res[i-1][j] != 0 and res[i][j - 1] == 0:
res[i][j] = res[i-1][j]%1000000007
if res[i-1][j] == 0 and res[i][j - 1] == 0:
res[i][j] = 0
else:
res[i][j] = 0
return res[x-1][y-1]
#
print Robot().countWays([[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,0,1,1],[0,1,1,1],[1,1,1,1],[1,1,1,1]],11,4)
发表于 2016-12-08 10:25:45
回复(0)
dp[i][j]表示，从(0,0)到（i， j）的走法数
1. 如果map[0][0]，则一个机器人不可能从(0,0)走到(x - 1,y - 1)
2. 否则，dp[0][0]=1，现在计算dp[i][j]值：
第一列：
if （i，0）为障碍，则dp[i][0]=0, 否则取决于前一点值dp[i-1][0]
第一行：
if （0，i）为障碍，则dp[0][i]=0, 否则取决于前一点值dp[0][i-1]
其他点：
if （i，j）为障碍，则dp[i][j]=0，否则取决于上方点和左方点的值之和dp[i-1][j]+dp[i][j-1]
int countWays(vector<vector<int> > map, int x, int y) {
if(map[0][0]==0)
return 0;
vector<vector<int> > dp(x, vector<int>(y, 0));
dp[0][0]=1;
for(int i=1; i<x; i++)
dp[i][0]=map[i][0]==1?dp[i-1][0]:0;
for(int i=1; i<y; i++)
dp[0][i]=map[0][i]==1?dp[0][i-1]:0;
for(int i=1; i<x; i++){
for(int j=1; j<y; j++)
dp[i][j]=map[i][j]==0?0:(dp[i-1][j]+dp[i][j-1])%1000000007;
}
return dp[x-1][y-1];
}
编辑于 2016-10-28 17:26:19
回复(1)
问题信息
难度：
85条回答
152收藏
115219浏览
通过挑战的用户
查看代码-
2023-02-16 19:44:59
-
2023-02-14 15:11:01 -
2023-02-13 23:05:55 -
2022-12-01 09:45:16 -
2022-10-14 23:46:04
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
