LintCode 1479: Can Reach Th Endpoint (BFS 典型题)

Solution 1: BFS searching， 类似骑士遍历题。

struct Coord {
  int x;
  int y;
  Coord() : x(0), y(0) {}
  Coord(int a, int b) : x(a), y(b){}
};

class Solution {
public:
    /**
     * @param map: the map
     * @return: can you reach the endpoint
     */
 
    bool reachEndpoint(vector<vector<int>> &grid) {
        vector<int> dirX = {1, -1, 0, 0};
        vector<int> dirY = {0, 0, 1, -1};
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));

        queue<Coord> q;
        q.push(Coord(0, 0));
        // int steps = 0; //for this question, it does not need steps as it just returns true/false.
        
        while (!q.empty()) {
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i) {
                Coord p = q.front();
                q.pop();
                
                if (grid[p.x][p.y] == 9) return true;
                
                for (int j = 0; j < 4; ++j) {
                    Coord neighbor = Coord(p.x + dirX[j], p.y + dirY[j]);
                    
                    //check if 1) p is inside of the grid; 2) not obstacle; 3) unvisited 
                    if (neighbor.x >=0 && neighbor.x < grid.size() && 
                        neighbor.y >=0 && neighbor.y < grid[0].size() &&
                        (grid[neighbor.x][neighbor.y] != 0) &&
                        !visited[neighbor.x][neighbor.y]) {
                        
                        q.push(neighbor);
                        visited[neighbor.x][neighbor.y] = true;
                    }
                }
            }
            //steps++;
        }
        
        return false;
    }
};

解法2：DFS searching (方向为从上到下，从左到右， 这样不需考虑重复访问情况)，代码很短，能pass，但我觉得不对，因为实际上有可能要从下到上，从右到左才能绕到终点。先做个参考。

class Solution {
public:
    /**
     * @param map: the map
     * @return: can you reach the endpoint
     */
    bool reachEndpoint(vector<vector<int>> &grid) {
        return helper(grid, 0, 0);
    }

private:
    bool helper(vector<vector<int>> &grid, int x, int y) {
        if ((x == grid.size()) || (y == grid[0].size())) return false;
        
        if (grid[x][y] == 9) return true;
        
        if (grid[x][y] == 0) return false;
        
        return helper(grid, x + 1, y) || helper(grid, x, y + 1);
    }
};

解法3：类似解法1和解法2的综合。
注意
if (grid[newX][newY] == 1) grid[newX][newY] = 0;
这里必须加if, 否则就会把终点也update成obstacle了。

class Solution {
public:
    /**
     * @param map: the map
     * @return: can you reach the endpoint
     */
    bool reachEndpoint(vector<vector<int>> &grid) {
        return helper(grid, 0, 0);
    }

    vector<int> dirX = {1, -1, 0, 0};
    vector<int> dirY = {0, 0, 1, -1};

private:
    bool helper(vector<vector<int>> &grid, int x, int y) {
    
        if (grid[x][y] == 9) return true;

        for (int i = 0; i < 4; ++i) {
            int newX = x + dirX[i];
            int newY = y + dirY[i];
           
            //遇墙返回，遇障碍返回，访问过等同于遇障碍。
            if (newX < 0 || newX >= grid.size() || 
                newY < 0 || newY >= grid[0].size() ||
                grid[newX][newY] == 0) {
            
                continue;
            }
            
            //we need to add if (grid[newX][newY] == 1), otherwise, it may change the destination (=9) to 0 also.
            if (grid[newX][newY] == 1) grid[newX][newY] = 0;
    
            if (helper(grid, newX, newY)) return true;   //if (dfs(,,,) is false, cannot return now, still dfs.
        }    
        
        return false;
     }
};

解法4: DP
这题也可以用DP做，但有个问题是终点不一定是右下角，所以要在DP过程中判断是不是到了终点，然后返回。
下次再做。