Castle On The Grid - HackerRank

https://www.hackerrank.com/challenges/castle-on-the-grid

You are given a grid with both sides equal to N$N$. Rows and columns are numbered from 0$0$ to N−1$N-1$. There is a castle on the intersection of the a$a$^th row and the b$b$^th column.

Your task is to calculate the minimum number of steps it would take to move the castle from its initial position to the goal position (c,d$c,d$).

It is guaranteed that it is possible to reach the goal position from the initial position.

Note: You can move the castle from cell (a,b)$(a,b)$ to any (x,y)$(x,y)$ in a single step if there is a straight line between (a,b)$(a,b)$ and (x,y)$(x,y)$ that does not contain any forbidden cell. Here, "X" denotes a forbidden cell.

3
.X.
.X.
...
0 0 0 2

3

Explanation

Here is a path that one could follow in order to reach the destination in 3$3$ steps:

(0,0)−>(2,0)−>(2,2)−>(0,2)$(0,0)->(2,0)->(2,2)->(0,2)$.

https://www.hackerrank.com/rest/contests/master/challenges/castle-on-the-grid/hackers/phishman3579/download_solution

    private static final int INVALID    = Integer.MAX_VALUE;
    private static final int UNVISITED  = Integer.MAX_VALUE-1;

    private static final class Board {

        final int N;
        final int[][] board;

        private Board(int N, char[][] chars) {
            this.N = N;

            this.board = new int[N][N];
            for (int i=0; i<N; i++)
                for (int j=0; j<N; j++) {
                    if (chars[i][j]=='X')
                        board[i][j] = INVALID;
                    else
                        board[i][j] = UNVISITED;
                }
        }
    }

    private static final Board populateBoard(int N, int a, int b, int c, int d, char[][] chars) {
        final Board visited = new Board(N,chars);

        final Deque<Integer[]> queue = new ArrayDeque<Integer[]>();
        queue.add(new Integer[]{a,b});
        visited.board[a][b] = 0;

        while (!queue.isEmpty()) {
            final Integer[] next = queue.removeFirst();
            final int ta = next[0];
            final int tb = next[1];
            final int nextValue = visited.board[ta][tb]+1;

            //System.out.println(visited.toString());
            if (ta==c && tb==d) {
                break;
            }

            for (int i=ta-1; i>=0; i--) {
                int na = i;
                int nb = tb;
                if (visited.board[na][nb] == UNVISITED) {
                    visited.board[na][nb] = nextValue;
                    queue.addLast(new Integer[]{na,nb});
                } else {
                    break;
                }
            }
            for (int i=tb-1; i>=0; i--) {
                int na = ta;
                int nb = i;
                if (visited.board[na][nb] == UNVISITED) {
                    visited.board[na][nb] = nextValue;
                    queue.addLast(new Integer[]{na,nb});
                } else {
                    break;
                }
            }
            for (int i=ta+1; i<N; i++) {
                int na = i;
                int nb = tb;
                if (visited.board[na][nb] == UNVISITED) {
                    visited.board[na][nb] = nextValue;
                    queue.addLast(new Integer[]{na,nb});
                } else {
                    break;
                }
            }
            for (int i=tb+1; i<N; i++) {
                int na = ta;
                int nb = i;
                if (visited.board[na][nb] == UNVISITED) {
                    visited.board[na][nb] = nextValue;
                    queue.addLast(new Integer[]{na,nb});
                } else {
                    break;
                }
            }
        }

        return visited;
    }

https://www.hackerrank.com/rest/contests/master/challenges/castle-on-the-grid/hackers/acetseng/download_solution

    public static int[][] steps=null;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        steps=new int[N][N];
        char[][] board=new char[N][N];
        for(int i=0; i<N; i++) {
            String s=sc.next();
            board[i]=s.toCharArray();
            Arrays.fill(steps[i], -1);
        }
        int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), d=sc.nextInt();
        System.out.println(getSteps(board, a, b, c, d));
    }
    public static int getSteps(char[][] board, int a, int b, int c, int d) {
        // a,b  --> c,d
        Queue<D> que=new LinkedList<D>();
        Queue<D> nextlevel;
        que.offer(new D(c, d));
        int s=0, n=board.length;
        while(!que.isEmpty()) {
            nextlevel=new LinkedList<D>();
            while(!que.isEmpty()) {
                D cur=que.poll();
                int x=cur.x, y=cur.y;
                if(a==x && b==y)
                    return s;
                steps[x][y]=s;
                for(int j=y-1; j>=0; j--) { //left
                    if(board[x][j]=='X')
                        break;
                    nextlevel.offer(new D(x, j));
                    board[x][j]='X';
                }
                for(int j=y+1; j<n; j++) { //right
                    if(board[x][j]=='X')
                        break;
                    nextlevel.offer(new D(x, j));
                    board[x][j]='X';
                }
                for(int i=x-1; i>=0; i--) { //up
                    if(board[i][y]=='X')
                        break;
                    nextlevel.offer(new D(i, y));
                    board[i][y]='X';
                }
                for(int i=x+1; i<n; i++) {
                    if(board[i][y]=='X')
                        break;
                    nextlevel.offer(new D(i, y));
                    board[i][y]='X';
                }
            }
            s+=1;
            que=nextlevel;
        }
        return s;
    }
class D{
    int x;
    int y;
    public D(int x, int y) {
        this.x=x; 
        this.y=y;
    }
}

https://www.hackerrank.com/rest/contests/master/challenges/castle-on-the-grid/hackers/rixiac/download_solution

Use recursive to implement BFS

    static void go(List<int[]> l , int[][] map ){
        int[] xy = l.get(0);
        l.remove(0);
        int x = xy[0];
        int y = xy[1];
        int temp = x ;
        int n = map[x][y] + 1 ;
        while(--temp >= 0 && (map[temp][y] == 0 || map[temp][y] >= n)){
            map[temp][y] = n;
            l.add(new int[]{temp,y});
        }
        temp = x ;
        while(++temp < map.length && (map[temp][y] == 0 || map[temp][y] >= n)){
            map[temp][y] = n;
            l.add(new int[]{temp,y});
        }
        temp = y ;
        while(--temp >= 0 && (map[x][temp] == 0 || map[x][temp] >= n)){
            map[x][temp] = n;
            l.add(new int[]{x,temp});
        }
        temp = y ;
        while(++temp < map.length && (map[x][temp] == 0 || map[x][temp] >= n)){
            map[x][temp] = n;
            l.add(new int[]{x,temp});
        }
        if(l.size() > 0){
            go(l , map);
        }
    }

http://www.martinkysel.com/hackerrank-castle-on-the-grid-solution/

This solution works with the task as a 2D array. There are options available where you treat the task as a graph problem. In both cases each node it visited exactly once using BFS. On each node, I generate all nodes that are connected to this node in a straight line that is not broken by a ‘X’. I keep the distance data (integer) in the array itself. I store the nodes that have to be visited in a FIFO queue. Once the top element in the queue is the end, I terminate the algorithm. The data stored in the array are these:

• X        – blocked
• .          – not visited yet
• (int)   – already visited. Value is the number of steps from the beginning.

from collections import deque

 

class Point:

    def __init__(self, x, y):

        self.x = x

        self.y = y

     

    def __str__(self):

        return "X=%d,Y=%d" % (self.x, self.y)

 

def getPointsFromPoint(N, arr, point):

    x = point.x

    y = point.y

    points = []

     

    while x > 0:

        x -= 1

        if arr[x][y] == 'X':

            break

        points.append(Point(x,y))

     

    x = point.x

    while x < N-1:

        x += 1

        if arr[x][y] == 'X':

            break

        points.append(Point(x,y))

     

    x = point.x

    while y > 0:

        y -= 1

        if arr[x][y] == 'X':

            break

        points.append(Point(x,y))

     

    y = point.y

    while y < N-1:

        y += 1

        if arr[x][y] == 'X':

            break

        points.append(Point(x,y))

         

    return points

     

def solveCastleGrid(N, arr, start, end):

    q = deque([start])

    arr[start.x][start.y] = 0

     

    while q:

        current_point = q.pop()

        current_distance = arr[current_point.x][current_point.y]

         

        points = getPointsFromPoint(N, arr, current_point)

        for p in points:

            if arr[p.x][p.y] == '.':

                arr[p.x][p.y] = current_distance + 1

                q.appendleft(p)

                if p.x == end.x and p.y == end.y:

                    return current_distance + 1

    return -1

https://d396qusza40orc.cloudfront.net/algo1/slides/algo-graphs-bfs_typed.pdf