【多次过】Lintcode 1479. 能否到达终点

给一个大小为 m*n 的map，1 代表空地，0 代表障碍物，9代表终点。请问如果你从 (0, 0) 开始能否到达终点？

样例

样例1

输入: 
[
	[1,1,1],
	[1,1,1],
	[1,1,9]
]
输出: true

样例2

输入: 
[
	[1,1,1],
	[1,0,0],
	[1,0,9]
]
输出: false

---

解题思路1：

BFS

public class Solution {
    /**
     * @param map: the map
     * @return: can you reach the endpoint
     */
    public boolean reachEndpoint(int[][] map) {
        // Write your code here
        int n = map.length;
        int m = map[0].length;
        if (n == 0 || m == 0) 
            return false;
        
        Queue<Integer> q = new LinkedList<>();
        boolean[][] vis = new boolean[n][m];
        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};
        q.offer(0);
        vis[0][0] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            int curx = cur / m;
            int cury = cur % m;
            for (int i = 0; i < 4; i++) {
                int nx = curx + dx[i];
                int ny = cury + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || map[nx][ny] == 0)
                    continue;

                if (map[nx][ny] == 9) 
                    return true;

                q.offer(nx * m + ny);
                vis[nx][ny] = true;
            }
        }
        return false;
    }
}

解题思路2：

DFS

public class Solution {
    /**
     * @param map: the map
     * @return: can you reach the endpoint
     */
    public boolean reachEndpoint(int[][] map) {
        int row = map.length;
        if(row == 0)return false;
        int col = map[0].length;
        
        return dfs(row,col,0,0,map);
    }
    
    private boolean dfs(int row,int col,int x, int y, int[][] map){
        if(map[x][y] == 0)
            return false;
        if(map[x][y] == 9)
            return true;
            
        if(x+1<col && dfs(row,col,x+1,y,map))
            return true;

        if(y+1<row && dfs(row,col,x,y+1,map))
            return true;
            
        return false;
    }
}

or

public class Solution {
    int[] direction = new int[]{0, 1, 0, -1, 0};
    /**
     * @param map: the map
     * @return: can you reach the endpoint
     */
    public boolean reachEndpoint(int[][] map) {
       if (map == null || map.length == 0 || map[0].length == 0) 
            return false;
       
       return dfs(map, 0, 0);
    }
    
    private boolean dfs(int[][] map, int x, int y) {
        if (map[x][y] == 9) 
            return true;
        map[x][y] = 0;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + direction[i];
            int ny = y + direction[i + 1];
            
            if (isValid(map, nx, ny) && dfs(map, nx, ny)) 
                return true;
        }
        
        return false;
    }
    
    private boolean isValid(int[][] map, int x, int y) {
        return x >= 0 && y >= 0 && x < map.length && y < map[0].length && map[x][y] != 0;
    }
}