给定一个int[][] map(C++ 中为vector >)网格图,若map[i][j]为1则该点不是障碍点,否则为障碍点。另外给定int x,int y,表示网格的大小。现有一个机器人要从网格左上角走到右下角,只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出,并保证x和y均小于等于50。
给定一个int[][] map(C++ 中为vector >)网格图,若map[i][j]为1则该点不是障碍点,否则为障碍点。另外给定int x,int y,表示网格的大小。现有一个机器人要从网格左上角走到右下角,只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出,并保证x和y均小于等于50。
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]; } };
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]; }
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
优化空间为一维。
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;
}
};
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); }
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]; } }
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]; }
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]; } };
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]; } };
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]; } }
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;
}
# -*- 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]
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]; } }
/* *方法一非递归直接开数组(费空间) *方法二滚动数组(省空间) */ 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]; } }
思路:动态规划递归式为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]; } }
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; } };
#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)
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]; }