Castle on the Grid

Sort by

recency

|

9 Discussions

|

  • + 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; 
            }
    
  • + 0 comments

    Using BFS

    def is_valid(grid, i, j):
        return i >=0 and i < len(grid) and j >=0 and j < len(grid[i]) and grid[i][j] != 'X'
        
    def span(grid, x, y, graph):
        i, j = x+1, y
        while is_valid(grid, i, j):
            graph[(x, y)].add((i, j))
            i = i+1
        
        i, j = x-1, y
        while is_valid(grid, i, j):
            graph[(x, y)].add((i, j))
            i = i-1
            
        i, j = x, y+1
        while is_valid(grid, i, j):
            graph[(x, y)].add((i, j))
            j = j+1
        
        i, j = x, y-1
        while is_valid(grid, i, j):
            graph[(x, y)].add((i, j))
            j = j-1
        
    def build_graph(grid):
        graph = {}
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if (grid[i][j] != 'X'):
                    graph[(i, j)] = set()
                    span(grid, i, j, graph)
        return graph
    
    def bfs(start, end, graph):
        q1 = deque()
        q2 = deque()
        
        visited = set()
        
        q1.append(start)
        depth = 0
        
        while len(q1) > 0:
            v = q1.popleft()
            if v == end:
                return depth
            for adj in graph[v]:
                if adj not in visited:
                    visited.add(adj)
                    q2.append(adj)
            if len(q1) == 0 and len(q2) > 0:
                depth = depth + 1
                q1, q2 = q2, q1
        
        return depth
    
    def minimumMoves(grid, startX, startY, goalX, goalY):
        graph = build_graph(grid)
        start = (startX, startY)
        end = (goalX, goalY)
        return bfs(start, end, graph)
    
  • + 0 comments

    C#

    private sealed record PathPoint(int X, int Y, int Direction, int Moves);
    
    public static int MinimumMoves(List<string> grid, int startX, int startY, int goalX, int goalY)
    {
        var moveDistances = Enumerable.Range(0, grid.Count).Select(_ => Enumerable.Repeat(int.MaxValue, grid.Count).ToArray()).ToArray();
        var directions = new List<(int Dx, int Dy)> { (-1, 0), (0, -1), (0, 1), (1, 0) };
        var pathQueue = new Queue<PathPoint>();
        var results = new List<int>();
    
        moveDistances[startX][startY] = 0;
        pathQueue.Enqueue(new PathPoint(startX, startY, -1, 0));
    
        while (pathQueue.TryDequeue(out var path))
        {
            if (path.X == goalX && path.Y == goalY)
            {
                results.Add(path.Moves);
            }
    
            for (var i = 0; i < directions.Count; i++)
            {
                var (x, y) = (path.X + directions[i].Dx, path.Y + directions[i].Dy);
                if (x >= 0 && x < grid.Count && y >= 0 && y < grid.Count && grid[x][y] != 'X')
                {
                    var moves = path.Moves + (i == path.Direction ? 0 : 1);
                    if (moves < moveDistances[x][y])
                    {
                        moveDistances[x][y] = moves;
                        pathQueue.Enqueue(new PathPoint(x, y, i, moves));
                    }
                }
            }
        }
    
        return results.Min();
    }
    
  • + 0 comments

    JavaScript

    function minimumMoves(grid, startX, startY, goalX, goalY) {
        // Write your code here
        const queue = [[startX, startY, 0]];
        const visited = new Set();
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
        while (queue.length > 0) {
            const [x, y, moves] = queue.shift();
            const position = `${x}-${y}`;
    
            if (x === goalX && y === goalY) {
                return moves;
            }
    
            visited.add(position);
    
            for (const [dx, dy] of directions) {
                let newX = x + dx;
                let newY = y + dy;
    
                while (
                    newX >= 0 &&
                    newY >= 0 &&
                    newX < grid.length &&
                    newY < grid.length &&
                    grid[newX][newY] !== 'X'
                ) {
                    const newPosition = `${newX}-${newY}`;
    
                    if (!visited.has(newPosition)) {
                        queue.push([newX, newY, moves + 1]);
                        visited.add(newPosition);
                    }
    
                    newX += dx;
                    newY += dy;
                }
            }
        }
    
        return -1; // If a path is not found
    }
    
  • + 0 comments

    Java8 using Dijkstra and TreeSet

    class DijkstraNode implements Comparable<DijkstraNode> {
        private final int X;
        private final int Y;
        private int onStep;
        
        public DijkstraNode(int x, int y, int onStep) {
            this.X = x;
            this.Y = y;
            this.onStep = onStep;
        }
            
        public int getOnStep() {
            return onStep;
        }
        
        public void setOnStep(int onStep) {
            this.onStep = onStep;
        }
        
        public int getX() {
            return X;
        }
        
        public int getY() {
            return Y;
        }
        
        @Override
        public int compareTo(DijkstraNode node) {
            return this.X != node.getX() ? (this.X - node.getX()) : (this.Y - node.getY());
        }
        
    }
    
    class Result {
    
        /*
         * Complete the 'minimumMoves' function below.
         *
         * The function is expected to return an INTEGER.
         * The function accepts following parameters:
         *  1. STRING_ARRAY grid
         *  2. INTEGER startX
         *  3. INTEGER startY
         *  4. INTEGER goalX
         *  5. INTEGER goalY
         */
        
        public static TreeSet<DijkstraNode> findNeighbors(List<String> grid, int x, int y, int onStep, TreeSet<DijkstraNode> alreadyParsed, DijkstraNode goal) {
            
            TreeSet<DijkstraNode> set = new TreeSet<>();
            
            int n = grid.size();
            int m = grid.get(0).length();
            
            for (int i = x + 1; i < n; i++) {
                int j = y;    
                if (grid.get(i).charAt(j) == 'X') {
                    break;
                }
                DijkstraNode node = new DijkstraNode(i, j, onStep);
                if (alreadyParsed.contains(node)) {
                    break;
                }
                if (node.compareTo(goal) == 0) {
                    goal.setOnStep(onStep);
                }
                set.add(node);
            }
            
            for (int i = x - 1; i >= 0; i--) {
                int j = y;
                if (grid.get(i).charAt(j) == 'X') {
                    break;
                }
                DijkstraNode node = new DijkstraNode(i, j, onStep);
                if (alreadyParsed.contains(node)) {
                    break;
                }
                if (node.compareTo(goal) == 0) {
                    goal.setOnStep(onStep);
                }
                set.add(node);
            }
            
            for (int j = y + 1; j < m; j++) {
                int i = x;
                if (grid.get(i).charAt(j) == 'X') {
                    break;
                }
                DijkstraNode node = new DijkstraNode(i, j, onStep);
                if (alreadyParsed.contains(node)) {
                    break;
                }
                if (node.compareTo(goal) == 0) {
                    goal.setOnStep(onStep);
                }
                set.add(node);
            }
            
            for (int j = y - 1; j >= 0; j--) {
                int i = x;
                if (grid.get(i).charAt(j) == 'X') {
                    break;
                }
                DijkstraNode node = new DijkstraNode(i, j, onStep);
                if (alreadyParsed.contains(node)) {
                    break;
                }
                if (node.compareTo(goal) == 0) {
                    goal.setOnStep(onStep);
                }
                set.add(node);
            }
            return set;
        }
        
        public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {
    
            DijkstraNode node = new DijkstraNode(startX, startY, 0);
            
            DijkstraNode goal = new DijkstraNode(goalX, goalY, 0);
                
            LinkedList<DijkstraNode> queue = new LinkedList<>();
            
            TreeSet<DijkstraNode> alreadyParsed = new TreeSet<>();
                    
            queue.add(node);
            alreadyParsed.add(node);
            
            while (!queue.isEmpty()) {
                DijkstraNode primary = queue.pollFirst();
                
                int x = primary.getX();
                int y = primary.getY();
                
                int onStep = primary.getOnStep() + 1;
                
                TreeSet<DijkstraNode> neighbors = findNeighbors(grid, x, y, onStep, alreadyParsed, goal);
                
                if (neighbors.contains(goal)) {
                    break;
                }
                
                alreadyParsed.addAll(neighbors);
                queue.addAll(neighbors);
            } 
            return goal.getOnStep();
        }
    }