A checker game on an infinite board between players A and B is in progress. There are two types of pieces in checkers: pawns and queens. Pieces can move only diagonally and forward. A queen can move any number of steps in one of these two directions. If there is a piece belonging to player B on the line of player A's queen's movement, player A can beat it by leaping over it and optionally passing some more empty fields. Player A can beat only one of player B's pieces in one move. After beating one of player B's pieces in this way, player A can continue his turn and make another move, but only if he can beat another piece. Player A gains 1 point for beating a pawn and 10 points for beating a queen. Player A is left with his last piece: a queen. Now it is A's turn − the last turn in the game. Player A wants to know the maximum number of points he can score in a single turn. Can you help?
$Tis a string of N characters with pieces values. "p" and "q" represent player B's pawn and queen, and "X" represents player A's queen. Arrays
$Yare the x and y coordinates of pieces.
For example, given:
$X = [3, 5, 1, 6]; $Y = [1, 3, 3, 8];
$T = "Xpqp";
the function should return 10
Do you know a good DP (dynamic programming) algorithm that would find the solution for the problem efficiently? In my solution:
-I used the buffer for already found maximum possible scores for individual fields, so I don't do double checks.
-Also, I put all enemy (player B) pieces in a two dimensional array, for easier detection if there is enemy piece on a certain field (if [x][y] is not set, then there isn't).
-I am doing the check for each field that it didn't cross the border of no possibility of getting any more points (no more pieces to be beaten beyond this point), so there are three borderlines:
a) one that limits the height (if we are on the same level as the highest enemy piece, no use checking if any more can be beaten, because there isn't)
b) two borders that are left and right diagonal that form the imagined border angle.
Despite this, I only got 46% on the assessment online test.