Castle on the Grid

  • + 0 comments

    Java O(n*n)

    public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {
                int n = grid.size();
                boolean[][] visited = new boolean[n][n];
                Queue<int[]> queue = new LinkedList<>();
                queue.offer(new int[]{startX, startY, 0});
                visited[startX][startY] = true;
    
                int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
                while (!queue.isEmpty()) {
                    int[] current = queue.poll();
                    int x = current[0];
                    int y = current[1];
                    int moves = current[2];
    
                    if (x == goalX && y == goalY) {
                        return moves;
                    }
    
                    for (int[] dir : directions) {
                        int newX = x + dir[0];
                        int newY = y + dir[1];
    
                        while (newX >= 0 && newX < n && newY >= 0 && newY < n && grid.get(newX).charAt(newY) == '.') {
                            if (!visited[newX][newY]) {
                                visited[newX][newY] = true;
                                queue.offer(new int[]{newX, newY, moves + 1});
                            }
                            newX += dir[0];
                            newY += dir[1];
                        }
                    }
                }
    
                return -1; 
            }