[8.2] Robot in a Grid
2024-09-21 19:38:20
Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are 'off limit' such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
Similar questions in Leetcode:
https://leetcode.com/problems/unique-paths/
public class Solution {
public int uniquePaths(int m, int n) {
int[][] paths = new int[m][n];
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(i == 0 && j == 0) {
paths[0][0] = 1;
} else {
paths[i][j] = (i==0 ? 0: paths[i - 1][j]) + (j ==0 ? 0: paths[i][j - 1]);
}
}
}
return paths[m - 1][n - 1];
}
}
https://leetcode.com/problems/unique-paths-ii/
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
return 0;
}
int[][] dp = new int[m][n];
dp[0][0] = 1;
for(int i = 1; i < n; ++i) {
if(obstacleGrid[0][i] == 0) {
dp[0][i] = dp[0][i - 1];
} else {
dp[0][i] = 0;
}
}
for(int i = 1; i < m; ++i) {
if(obstacleGrid[i][0] == 0) {
dp[i][0] = dp[i-1][0];
} else {
dp[i][0] = 0;
}
}
for(int i = 1; i < m; ++i) {
for(int j = 1; j < n; ++j) {
if(obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j - 1];
} else {
dp[i][j] = 0;
}
}
}
return dp[m - 1][n - 1];
}
}
最新文章
- js之路
- IDA在内存中dump出android的Dex文件
- HTML 学习笔记(列表)
- Mysql的简单使用（三）
- Quartz作业调度框架
- BLE-NRF51822教程16-BLE地址
- 【20160924】GOCVHelper MFC增强算法（3）
- HNOI2004宠物收养所（平衡树）
- [iOS微博项目 - 1.6] - 自定义TabBar
- DEDECMS中，list标签和pagelist标签
- Node.js REPL终端
- 【录音】Android录音--AudioRecord、MediaRecorder
- 深入Java虚拟机——类型装载、连接（转）
- 数据库 MySQL基础知识
- [ExtJS5学习笔记]第三十四节 sencha extjs 5 grid表格之java后台导出excel
- C#实现物联网系统温度解析的函数（支持补码）
- Python 包、模块、函数、变量作用域
- 使用select函数改进客户端/服务器端程序
- linux用户及用户组操作
- Block Towers---cf626c（二分）