lintcode 787. The Maze 、788. The Maze II 、
2024-09-26 12:39:42
787. The Maze
https://www.cnblogs.com/grandyang/p/6381458.html
与number of island不一样，递归的函数返回值是bool，不是void。
maze = -1用来表示已经访问的节点。
dp用来记录每个位置的是否能访问，如果dp != -1，就表示这个地方已经访问过了，可以避免多余的访问。
一直滑动用while循环来做，这里并没有没移动一次就增加一个访问。
int x = i,y = j必须这样写，因为之后的4种迭代都是从i、j这个位置出发，x、y在每一次迭代过程中已经发生了变化。
vector的初始化用{}，如果是vector<vector<int>>，初始化用{{},{},{}}
class Solution {
public:
/**
* @param maze: the maze
* @param start: the start
* @param destination: the destination
* @return: whether the ball could stop at the destination
*/
bool hasPath(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) {
// write your code here
int m = maze.size();
if(m <= )
return false;
int n = maze[].size();
if(n <= )
return false;
vector<vector<int>> dp(m,vector<int>(n,-));
return hasPath(maze,dp,start[],start[],destination[],destination[]);
}
bool hasPath(vector<vector<int>>& maze,vector<vector<int>>& dp,int i,int j,int di,int dj){
if(i == di && j == dj)
return true;
if(dp[i][j] != -)
return dp[i][j];
maze[i][j] = -;
int m = maze.size(),n = maze[].size();
bool res = false;
for(auto dir : dirs){
int x = i,y = j;
while(x >= && x < m && y >= && y < n && maze[x][y] != ){
x += dir[];
y += dir[];
}
x -= dir[];
y -= dir[];
if(maze[x][y] != -)
res |= hasPath(maze,dp,x,y,di,dj);
}
return res;
}
vector<vector<int>> dirs{{,-},{,},{,},{-,}};
};
自己写了一遍：
因为一直移动，所以需要一直进行dir的移动计算，直到不满足条件。
注意，这里
maze[new_x][new_y] != 1
而不是写的==0，对于-1的位置，也就是已经遍历过的点，你还是可以继续经过这里去其他地方。这个-1更多的是表示从这个点出发已经访问过了。
class Solution {
public:
/**
* @param maze: the maze
* @param start: the start
* @param destination: the destination
* @return: whether the ball could stop at the destination
*/
bool hasPath(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) {
// write your code here
if(maze.empty())
return false;
if(maze[].empty())
return false;
if(start.empty() || destination.empty())
return false;
return hasPath(maze,start[],start[],destination[],destination[]);
}
bool hasPath(vector<vector<int>>& maze,int x,int y,int destination_x,int destination_y){
if(x == destination_x && y == destination_y)
return true;
maze[x][y] = -;
bool flag = false;
for(int i = ;i < dirs.size();i++){
int new_x = x;
int new_y = y;
while(new_x >= && new_x < maze.size() && new_y >= && new_y < maze[].size() && maze[new_x][new_y] != ){
new_x += dirs[i][];
new_y += dirs[i][];
}
new_x -= dirs[i][];
new_y -= dirs[i][];
if(maze[new_x][new_y] != -)
flag |= hasPath(maze,new_x,new_y,destination_x,destination_y);
}
return flag;
}
vector<vector<int>> dirs{{-,},{,},{,-},{,}};
};
788. The Maze II
思路：用一个矩阵记录到每个位置的最短距离，初始化为INT_MAX，如果终点到最后仍然为INT_MAX，则表明不可达
错误解法一：
这个解法使用了visited数组，表示已经被访问过，这容易造成有些地方不可达。如果从另一个方向到当前位置
class Solution {
public:
/**
* @param maze: the maze
* @param start: the start
* @param destination: the destination
* @return: the shortest distance for the ball to stop at the destination
*/
int shortestDistance(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) {
// write your code here
int m = maze.size();
if(m <= )
return -;
int n = maze[].size();
if(n <= )
return -;
if(maze[start[]][start[]] == || maze[destination[]][destination[]] == )
return -;
vector<vector<int>> distance(m,vector<int>(n,INT_MAX));
vector<vector<bool>> visited(m,vector<bool>(n,false));
queue<pair<int,int>> q;
q.push(make_pair(start[],start[]));
distance[start[]][start[]] = ;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
visited[x][y] = true;
for(auto dir : dirs){
int x_new = x + dir[];
int y_new = y + dir[];
int des = distance[x][y];
while(x_new >= && x_new < m && y_new >= && y_new < n && !visited[x_new][y_new] && maze[x_new][y_new] == ){
x_new += dir[];
y_new += dir[];
des++;
}
x_new -= dir[];
y_new -= dir[];
if(des < distance[x_new][y_new]){
distance[x_new][y_new] = des;
if(x_new != destination[] || y_new != destination[])
q.push(make_pair(x_new,y_new));
}
}
}
return distance[destination[]][destination[]] == INT_MAX ? - : distance[destination[]][destination[]];
}
vector<vector<int>> dirs{{-,},{,-},{,},{,}};
};
错误解法二：
class Solution {
public:
/**
* @param maze: the maze
* @param start: the start
* @param destination: the destination
* @return: the shortest distance for the ball to stop at the destination
*/
int shortestDistance(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) {
// write your code here
int m = maze.size();
if(m <= )
return -;
int n = maze[].size();
if(n <= )
return -;
if(maze[start[]][start[]] == || maze[destination[]][destination[]] == )
return -;
vector<vector<int>> distance(m,vector<int>(n,INT_MAX));
queue<pair<int,int>> q;
q.push(make_pair(start[],start[]));
distance[start[]][start[]] = ;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
int des = distance[x][y];
for(auto dir : dirs){
int x_new = x + dir[];
int y_new = y + dir[];
while(x_new >= && x_new < m && y_new >= && y_new < n && maze[x_new][y_new] == ){
x_new += dir[];
y_new += dir[];
des++;
}
x_new -= dir[];
y_new -= dir[];
if(des < distance[x_new][y_new]){
distance[x_new][y_new] = des;
if(x_new != destination[] || y_new != destination[])
q.push(make_pair(x_new,y_new));
}
}
}
return distance[destination[]][destination[]] == INT_MAX ? - : distance[destination[]][destination[]];
}
vector<vector<int>> dirs{{-,},{,-},{,},{,}};
};
正确解法：
class Solution {
public:
/**
* @param maze: the maze
* @param start: the start
* @param destination: the destination
* @return: the shortest distance for the ball to stop at the destination
*/
int shortestDistance(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) {
// write your code here
int m = maze.size();
if(m <= )
return -;
int n = maze[].size();
if(n <= )
return -;
if(maze[start[]][start[]] == || maze[destination[]][destination[]] == )
return -;
vector<vector<int>> distance(m,vector<int>(n,INT_MAX));
queue<pair<int,int>> q;
q.push(make_pair(start[],start[]));
distance[start[]][start[]] = ;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(auto dir : dirs){
int x_new = x + dir[];
int y_new = y + dir[];
int des = distance[x][y];
while(x_new >= && x_new < m && y_new >= && y_new < n && maze[x_new][y_new] == ){
x_new += dir[];
y_new += dir[];
des++;
}
x_new -= dir[];
y_new -= dir[];
if(des < distance[x_new][y_new]){
distance[x_new][y_new] = des;
if(x_new != destination[] || y_new != destination[])
q.push(make_pair(x_new,y_new));
}
}
}
return distance[destination[]][destination[]] == INT_MAX ? - : distance[destination[]][destination[]];
}
vector<vector<int>> dirs{{-,},{,-},{,},{,}};
};
最新文章
- Visulalize Boost Voronoi in OpenSceneGraph
- 你需要知道的包管理器（Package Manager）
- struts2 错误提示页面
- 如何使用 vimdiff 来 git diff /svn diff
- SVG裁剪和平移的顺序
- array，vertor，arraylist，hashable，hashmap等几个易混淆概念的区别
- js跳转页面方法（转）
- POJ 2287 Tian Ji -- The Horse Racing（贪心）
- checkbox prop()函数
- Asp.Net WebApi+Microsoft.AspNet.WebApi.Core 启用CORS跨域访问
- /调整button的title的位置
- jqmobile
- EMC在线测试题目及答案 绿色为正确答案，红色为错误答案
- 暑假OI规划
- 507. Perfect Number
- sudo: java 找不到命令
- 【js】【图片显示】js控制html页面显示图片方式
- SoapUI、Jmeter、Postman三种接口测试工具的比较分析
- Linux 文件特殊权限_013
- ·通过wifi_scan学习esp32wifi程序编写
热门文章
- Linux系统运维相关的面试题 （问答题）
- python中的嵌套类
- django-ContentType的简单使用
- 51nod 2517 最少01翻转次数
- UVA1194 Machine Schedule[二分图最小点覆盖]
- httpclient: 设置连接池及超时配置，请求数据:PoolingHttpClientConnectionManager
- Codeforces Round #604 (Div. 2) A. Beautiful String
- POJ - 3252 - Round Numbers(数位DP）
- javaweb学习笔记（三）
- Kafka ISR and AR HW 、 LEO