https://www.hackerrank.com/challenges/castle-on-the-grid
https://www.hackerrank.com/rest/contests/master/challenges/castle-on-the-grid/hackers/phishman3579/download_solution
https://d396qusza40orc.cloudfront.net/algo1/slides/algo-graphs-bfs_typed.pdf
You are given a grid with both sides equal to . Rows and columns are numbered from to . There is a castle on the intersection of the th row and the 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 ().
It is guaranteed that it is possible to reach the goal position from the initial position.
Note: You can move the castle from cell to any in a single step if there is a straight line between and that does not contain any forbidden cell. Here, "X" denotes a forbidden cell.
3
.X.
.X.
...
0 0 0 23
Explanation
Here is a path that one could follow in order to reach the destination in steps:
.
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;
}
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;
}
}
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 dequeclass 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 -1https://d396qusza40orc.cloudfront.net/algo1/slides/algo-graphs-bfs_typed.pdf
