Sort by

recency

|

338 Discussions

|

2 weeks ago+ 0 comments

#!/bin/python3

import math
import os
import random
import re
import sys

#
# 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
#

from collections import deque

def minimumMoves(grid, startX, startY, goalX, goalY):
    n = len(grid)
    m = len(grid[0])
    
    # Store visited cells to avoid cycles and redundant processing
    visited = set()
    
    # Queue stores tuples of (x, y, moves)
    queue = deque([(startX, startY, 0)])
    visited.add((startX, startY))

    while queue:
        x, y, moves = queue.popleft()
        
        if x == goalX and y == goalY:
            return moves

        # Define the four cardinal directions
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        for dx, dy in directions:
            nx, ny = x, y
            
            # Slide as far as possible in the current direction
            while True:
                nx += dx
                ny += dy
                
                # Check bounds and for obstacles
                if not (0 <= nx < n and 0 <= ny < m and grid[nx][ny] != 'X'):
                    break # Stop sliding if out of bounds or an obstacle is hit
                
                # Only add the final destination of the slide to the queue
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, moves + 1))
    
    # Goal is unreachable
    return -1

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    grid = []
    for _ in range(n):
        grid.append(input())

    startX, startY, goalX, goalY = map(int, input().rstrip().split())

    result = minimumMoves(grid, startX, startY, goalX, goalY)

    fptr.write(str(result) + '\n')

    fptr.close()

2 weeks ago+ 0 comments

Solution in Python

#!/bin/python3

import math
import os
import random
import re
import sys

#
# 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
#

from collections import deque

def minimumMoves(grid, startX, startY, goalX, goalY):
    # Write your code here
    n = len(grid)
    m = len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]    
    queue = deque([(startX, startY, 0)])  
    visited = set()
    visited.add((startX, startY))
    while queue:
        x, y, moves = queue.popleft()        
        if (x, y) == (goalX, goalY):
            return moves        
        for dx, dy in directions:
            nx, ny = x, y
            while 0 <= nx + dx < n and 0 <= ny + dy < m and grid[nx + dx][ny + dy] != 'X':
                nx += dx
                ny += dy
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, moves + 1))    
    return -1

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    grid = []

    for _ in range(n):
        grid_item = input()
        grid.append(grid_item)

    first_multiple_input = input().rstrip().split()

    startX = int(first_multiple_input[0])

    startY = int(first_multiple_input[1])

    goalX = int(first_multiple_input[2])

    goalY = int(first_multiple_input[3])

    result = minimumMoves(grid, startX, startY, goalX, goalY)

    fptr.write(str(result) + '\n')

    fptr.close()

1 month ago+ 0 comments

My Java 8 solution, passing all test-cases, for a Max Score of 30:

The core idea is to implement a Breadth-First-Search (BFS) of a Queue of Points, expanding the search in all four directions (Up, Down, Left, Right) - and sliding along each direction - till we reach either a boundary or an obstacle ('X'), and add each "unvisited" point into the Queue of Points. And all throughout, we keep track of visited (boolean) & visited (distances) for points visited along the BFS. We keep doing this either till the Queue is EMPTY (in which case we have NOT been able to reach the Goal), or till we reach the Goal Point.

This is guaranteed to give us optimal solution, in O(n^2) time.

Ignore the "vDbg" statements, as those are just for diagnostic / debug purposes, to understand the logic or debug better. You can enable / disable it via the "vDbg" flag. If enabled, it might slow execution time, resulting in failing some test-cases due to TLEs. I

class Result {

    // Only given for Diagnostic / Debug purposes.
    // Enabling this might result in slower execution.
    // Hence, it might fail test-cases with TLEs.
    private static final boolean vDbg = false;
    
    private static class Point {
        int rowIdx, colIdx;

        Point(int rowIdx, int colIdx) {
            this.rowIdx = rowIdx; this.colIdx = colIdx;
        }
        
        @Override
        public String toString() {
            return "(" + rowIdx + "," + colIdx + ")";
        }
    }

    /*
     * 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 int minimumMoves(List<String> grid, 
                      int startX, int startY, int goalX, int goalY) {
        // Write your code here
        int n = grid.size();

        // "visited[i][j]" indicates whether point (i,j) has been visited in BFS
        boolean[][] visited = new boolean[n][n];

        // "numMoves[i][j]" indicates the number of moves it takes to get to point (i,j)
        int[][] numMoves = new int[n][n];

        // Queue of Points, that's populated & de-populated during BFS
        Queue<Point> pointsQ = new ArrayDeque<>();

        // Initialize the Start Conditions for Breadth-First-Search (BFS)
        pointsQ.add(new Point(startX, startY));
        visited[startX][startY] = true;
        numMoves[startX][startY] = 0;

        // Direction Offsets along Rows / Columns
        // We can go four Directions: Up, Down, Left, Right
        int[] dirRowOffset = {1, -1, 0, 0};
        int[] dirColOffset = {0, 0, 1, -1};

        // Perform the Breadth-First-Search (BFS) using the Points Queue.
        while (!pointsQ.isEmpty()) {

            Point bfsPoint = pointsQ.poll();
            int curNumMoves = numMoves[bfsPoint.rowIdx][bfsPoint.colIdx];

            if (vDbg) {
                System.err.println(""); System.err.println("");
                System.err.println("pointsQ.size() = >" + pointsQ.size() + "< | " + 
                                   "bfsPoint = >" + bfsPoint + "< | " + 
                                   "curNumMoves = >" + curNumMoves + "<");
                System.err.println("pointsQ = >" + pointsQ + "<");
            }

            if (bfsPoint.rowIdx == goalX && bfsPoint.colIdx == goalY) {
                if (vDbg) { System.err.println("Success! Reached Goal in >" + 
                                               curNumMoves + "< moves!"); }
                return curNumMoves;
            }

            // Slide in all 4 directions
            for (int dirIdx = 0; dirIdx < 4; dirIdx++) {

                int nextRowIdx = bfsPoint.rowIdx + dirRowOffset[dirIdx];
                int nextColIdx = bfsPoint.colIdx + dirColOffset[dirIdx];

                if (vDbg) { System.err.println("Starting along DIR: " + 
                                               "dirIdx = >" + dirIdx + "< | " + 
                                               "nextRowIdx = >" + nextRowIdx + "< | " + 
                                               "nextColIdx = >" + nextColIdx + "<"); }

                // Slide in the SAME direction until boundary or blocked
                while ( nextRowIdx >= 0 && nextRowIdx < n && 
                        nextColIdx >= 0 && nextColIdx < n && 
                        grid.get(nextRowIdx).charAt(nextColIdx) == '.' ) {

                    if (vDbg) { System.err.println("Sliding along DIR: " + 
                                                   "dirIdx = >" + dirIdx + "< | " + 
                                                   "nextRowIdx = >" + nextRowIdx + "< | " + 
                                                   "nextColIdx = >" + nextColIdx + "< | " + 
                                                   "visited = >" + 
                                                   visited[nextRowIdx][nextColIdx] + "<"); }

                    if (!visited[nextRowIdx][nextColIdx]) {
                        
                        Point nextPoint = new Point(nextRowIdx, nextColIdx);

                        visited[nextRowIdx][nextColIdx] = true;
                        numMoves[nextRowIdx][nextColIdx] = (curNumMoves + 1);
                        pointsQ.add(nextPoint);

                        if (vDbg) { System.err.println("Adding new UNVISITED Point " + 
                                                       nextPoint + " into the Queue, " + 
                                                       "for further BFS."); }

                    }

                    // Slide further in the SAME direction
                    nextRowIdx += dirRowOffset[dirIdx];
                    nextColIdx += dirColOffset[dirIdx];

                }

            }

        }

        return -1;
    }

}

4 months ago+ 0 comments

Shouldn't test case 0 expect return value of 4? It expects 3, but i don't see how could it be done in 3 moves. All other test cases are green in my case.

5 months ago+ 0 comments

include

using namespace std;

struct Node { int x, y, moves; };

int minimumMoves(vector grid, int startX, int startY, int goalX, int goalY) { int n = grid.size(); vector> visited(n, vector(n, false)); queue q; q.push({startX, startY, 0}); visited[startX][startY] = true;

int dx[] = {-1, 1, 0, 0}; // up, down
int dy[] = {0, 0, -1, 1}; // left, right

while (!q.empty()) {
    Node curr = q.front();
    q.pop();

    if (curr.x == goalX && curr.y == goalY)
        return curr.moves;

    for (int dir = 0; dir < 4; ++dir) {
        int nx = curr.x;
        int ny = curr.y;
        while (true) {
            nx += dx[dir];
            ny += dy[dir];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n || grid[nx][ny] == 'X')
                break;

            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny, curr.moves + 1});
            }
        }
    }
}
return -1; // should never reach here if input guarantees a path

}

int main() { int n; cin >> n; vector grid(n); for (int i = 0; i < n; ++i) cin >> grid[i];

int startX, startY, goalX, goalY;
cin >> startX >> startY >> goalX >> goalY;

cout << minimumMoves(grid, startX, startY, goalX, goalY) << endl;

return 0; }

Sort by

|

338 Discussions

|

Solution in Python

include

include

include

Cookie support is required to access HackerRank