Leetcode 490) The Maze

06 Aug 2021 in Algorithms

내 답안

• 범위 조심

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] possibleStops = new boolean[maze.length][maze[0].length];
        possibleStops[start[0]][start[1]]=true;
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[]{start[0],start[1]});
        while(!q.isEmpty()){
            int size= q.size();
            for(int i=0;i<size;i++){
                int[] ind=q.poll();
                int a = ind[0];
                int b = ind[1];
                if(!(a<0 || a>maze.length || b<0 || b>maze[0].length)){
                    while(a<maze.length && maze[a][b]==0){
                        a++;
                    }
                    if(a-1>=0 && !possibleStops[a-1][b]){
                        q.add(new int[]{a-1,b});
                        possibleStops[a-1][b]=true;
                    }

                    a=ind[0];b = ind[1];
                    while(a>=0 && maze[a][b]==0){
                        a--;}
                    if(a+1<maze.length && !possibleStops[a+1][b]){
                        q.add(new int[]{a+1,b});
                        possibleStops[a+1][b]=true;

                    }

                    a=ind[0];b = ind[1];
                    while(b<maze[0].length && maze[a][b]==0){
                        b++;}
                    if(b-1>=0 && !possibleStops[a][b-1]){
                        q.add(new int[]{a,b-1});
                        possibleStops[a][b-1]=true;

                    }
                    a=ind[0];b=ind[1];
                    while(b>=0 && maze[a][b]==0){
                        b--;}
                    if(b+1<maze[0].length && !possibleStops[a][b+1]){
                        q.add(new int[]{a,b+1});
                        possibleStops[a][b+1]=true;

                    }                     
                }
            }
        }
        return possibleStops[destination[0]][destination[1]];
    }
}

다른 답안

class Solution {
    int[] xOffset = new int[]{0, 0, -1, 1};
    int[] yOffset = new int[]{1, -1, 0, 0};

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] seen = new boolean[maze.length][maze[0].length];
        return hasPathHelper(maze, start, destination, seen);

    }

    private boolean hasPathHelper(int[][] maze, int[] start, int[] des, boolean[][] seen) {
        if(seen[start[0]][start[1]] == true)
            return false;

        if(start[0] == des[0] && start[1] == des[1])
            return true;

        seen[start[0]][start[1]] = true;

        for(int i=0; i<4; i++) {
            int x = start[0] + xOffset[i];
            int y = start[1] + yOffset[i];
            while(x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0) {
                x = x + xOffset[i];
                y = y + yOffset[i];        
            }


            if(hasPathHelper(maze, new int[] {x-xOffset[i], y-yOffset[i]}, des, seen))
                return true;
        }
        //seen.remove(Arrays.asList(start[0], start[1]));
        return false;
    }
}