## Friday, April 8, 2016

### 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$. Rows and columns are numbered from $0$ to $N-1$. There is a castle on the intersection of the $a$th row and the $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$).
It is guaranteed that it is possible to reach the goal position from the initial position.
Note: You can move the castle from cell $\left(a,b\right)$ to any $\left(x,y\right)$ in a single step if there is a straight line between $\left(a,b\right)$ and $\left(x,y\right)$ 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$ steps:
$\left(0,0\right)->\left(2,0\right)->\left(2,2\right)->\left(0,2\right)$.

    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[]>();
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;
} 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;
} 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;
} 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;
} else {
break;
}
}
}

return visited;
}

    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> nextlevel;
que.offer(new D(c, d));
int s=0, n=board.length;
while(!que.isEmpty()) {
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;
}
}
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;
}
temp = x ;
while(++temp < map.length && (map[temp][y] == 0 || map[temp][y] >= n)){
map[temp][y] = n;
}
temp = y ;
while(--temp >= 0 && (map[x][temp] == 0 || map[x][temp] >= n)){
map[x][temp] = n;
}
temp = y ;
while(++temp < map.length && (map[x][temp] == 0 || map[x][temp] >= n)){
map[x][temp] = n;
}
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