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;
    }
};