Tutorial for The White Knight |
The White Knight problem asked in codechef contest(July 09) is really one of the simplest problems given in codechef contest. We are asked to find out the maximum number of black pawn that could be captured by white knight by moving in only right direction.
First thing we should observe is that knight can move in four positions. This could be visualized as tree with 4 branches (except at boundary condition). Knight could reach a position from multiple paths. This leads to overlapping sub problems so it should be solved using Dynamic programming.
We would move in a bottom-up(from right to left column) fashion and calculate for each position on the board, the maximum number of pawn that could be captured if White knight moves through that position. Since the total number of cell in board is n2 and calculation for each cell is done only once. So the overall complexity of algorithm is O(n2).
Algorithm:-
- Assign the board such that for a pawn at position (i,j) be have 1 and at empty position be have 0.
- Iterate right to left toward the white knight.
- For each position we would be calculate MAXIMUM of the 4 value that the knight can move from that position.
- Add this maximum value to the value at this position and assign newly calculated value for this position.
- Continue this process prior to the column of the white knight.
- Find the final result similarly.
Comments
What if we move from left to
What if we move from left to right? Won't it reduce some of the calculations??