LeetCode 面试题 08.02——迷路的机器人

本文主要是介绍LeetCode 面试题 08.02——迷路的机器人，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

2. 解题思路

此题就是一个典型的图搜索题，一种就是广度优先搜索，一种就是深度优先搜索。

3. 代码实现

class Solution {
public:vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {vector<vector<int> > ret;int row = obstacleGrid.size();if (row < 1) {return ret;}int col = obstacleGrid[0].size();if (col < 1) {return ret;}int total = row * col;vector<int> pre_node(total, -1);    // 上一个节点pre_node[0] = -2;vector<int> visited(total, false);  // 节点是否被访问queue<int> need_to_visit;// 第一个节点是否是障碍if (obstacleGrid[0][0] != 1) {need_to_visit.push(0);visited[0] = true;}while (!need_to_visit.empty()) {int cur_node = need_to_visit.front();int i = cur_node / col;int j = cur_node % col;int next_node = (i + 1) * col + j;if (i+1 < row && obstacleGrid[i+1][j] != 1 && !visited[next_node]) {visited[next_node] = true;pre_node[next_node] = cur_node;need_to_visit.push(next_node);if (next_node == total - 1) {break;}}next_node = i * col + j + 1;if (j+1 < col && obstacleGrid[i][j+1] != 1 && !visited[next_node]) {visited[next_node] = true;pre_node[next_node] = cur_node;need_to_visit.push(next_node);if (next_node == total - 1) {break;}}need_to_visit.pop();}if (!visited[total-1]) {return ret;}// 打印出路径int pre_node_id = total-1;while (pre_node_id != -2) {int i = pre_node_id / col;int j = pre_node_id % col;vector<int> temp = {i, j};ret.push_back(temp);pre_node_id = pre_node[pre_node_id];}reverse(ret.begin(), ret.end());return ret;}
};

class Solution {
public:vector<int> visited;    // 节点是否被访问bool find;              // 是否到达最后一个vector<vector<int> > ret;void dfs(vector<vector<int>>& obstacleGrid, int i, int j, int row, int col) {if (find)return;if (i * col + j == row * col - 1) {find = true;return;}int next_node = (i + 1) * col + j;if (i+1 < row && obstacleGrid[i+1][j] != 1 && !visited[next_node]) {visited[next_node] = true;vector<int> temp = {i+1, j};ret.push_back(temp);dfs(obstacleGrid, i+1, j, row, col);if (!find) {ret.pop_back(); } else {return;}}next_node = i * col + j + 1;if (j+1 < col && obstacleGrid[i][j+1] != 1 && !visited[next_node]) {visited[next_node] = true;vector<int> temp = {i, j+1};ret.push_back(temp);dfs(obstacleGrid, i, j+1, row, col);if (!find) {ret.pop_back(); }}}vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {int row = obstacleGrid.size();if (row < 1) {return ret;}int col = obstacleGrid[0].size();if (col < 1) {return ret;}visited = vector<int>(row*col, false);find = false;// 第一个节点是否是障碍if (obstacleGrid[0][0] != 1) {vector<int> temp = {0, 0};ret.push_back(temp);dfs(obstacleGrid, 0, 0, row, col);if (!find) {ret.pop_back(); }}return ret;}
};

这篇关于LeetCode 面试题 08.02——迷路的机器人的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---