CaptureThemAll – TopCoder

CaptureThemAll – TopCoder SRM 207 Div 2

This problem can be solved by BFS, and special care about chess rules.
When doing a check game, you can visit the same spot unlimitless  as long as the rules permit.
The Knight can move 8 directions, where the it move 2 position ( horizontal or vertical firest, then move one position to either direction that is perpendicular to the original move.)
So, for this problem, you don't need to check if the knight visited this spot already or not.
Rather, you have to clear the queue when you find a rook or queen, then add the spot into queue, and do the remaining search again. Also, it can only capture either rook or queen in the same move.
In pseudo code,

Create Queue q
Add the position of knight into q
while (queue is not empty) {
     current = pop the queue;
     if the current position is the rook or queen
          capture it, and clear queue.
          add current position to the queue
     if it captured two
           then return the current move
     Add neighbors of current to the queue
}

Here is problem statement.

Harry is playing magical chess. In this version of the game, all pieces move the same way as in regular chess, but players can cast some magical spells. Unfortunately, Harry's opponent, Joe, has captured all of Harry's pieces except one knight; Joe, on the other hand, still has a queen and a rook. The only chance Harry has to win this game is to cast a spell, "Haste", that will allow Harry's knight to make several moves in a row. You should determine the minimal number of moves the knight needs to capture both the rook and the queen, assuming neither of them moves. You may capture them in either order - rook first or queen first.  You will be given a String, knight, containing information about the knight. You will also be given a String, queen, and a String, rook, giving you information about Joe's pieces. knight, rook and queen will be formatted as "cr", where c is a character between 'a' and 'h', inclusive, determining the column on the board ('a' is the first column, 'h' is the last), and r is a digit between '1' and '8', inclusive, determining the row (1 is the lowest, 8 is the highest).

Here is my code written, and passed all tests.

import java.util.LinkedList;

public class CaptureThemAll {
public int fastKnight(String knight, String rook, String queen) {
boolean[][] joe = new boolean[8][8];
<8 i="" p=""><8 j="" p="">
int hx = Integer.valueOf(knight.substring(1))-1;
int hy = knight.charAt(0) - 'a';
joe[Integer.valueOf(rook.substring(1))-1][rook.charAt(0) - 'a'] = true;
joe[Integer.valueOf(queen.substring(1))-1][queen.charAt(0) - 'a'] = true;

LinkedList queue = new LinkedList();
queue.add(new Harry(hx,hy,0));
int[] captured = new int[4];

while (queue.size() > 0) {
Harry current = queue.removeFirst();
if (capture(current, joe, captured)) {
if (captured[0] != 1) {
captured[0] = 1;
captured[1] = current.move;
queue.clear();
queue.add(new Harry(current.x,current.y,current.move));
} else {
captured[2] = 1;
captured[3] = current.move;
}

}
if (captured[0] == 1 && captured[2] == 1)
return current.move;
addNeighbors(queue, current);
}

return -1;
}

public boolean capture(Harry harry, boolean[][] joe, int[] captured) {
if (joe[harry.x][harry.y]){
// only capture one in the same neighbors
if (!(captured[0] == 1 && captured[1] == harry.move)) {
joe[harry.x][harry.y] = false;
return true;
}
}

return false;
}

public void addNeighbors(LinkedList queue, Harry current) {
int[] dx = {-2,-2,2,2,-1,1,-1,1};
int[] dy = {-1,1,-1,1,-2,-2,2,2};
for (int i=0;i<8 i="" p=""> int x = current.x + dx[i];
int y = current.y + dy[i];
if (x >=0 && y >= 0 && x < 8 && y <8 br=""> queue.add(new Harry(x,y,current.move + 1));
}
}
}

class Harry{
int x;
int y;
int move;
public Harry(int xx, int yy, int m) {
x = xx;
y = yy;
move = m;
}
}

}