|This problem statement contains an image that may not display properly if viewed outside of the applet.
You play a game with your friend in which 16 square pieces are placed in a 4x4 grid on a board. Each piece has a distinct number between 1 and 16 written on it. A piece can be removed from the board if it is on an edge or if it can be dragged left, right, up or down through a path of unoccupied squares, until it leaves the board. When a piece is removed from the board, the square it occupied becomes unoccupied.
On the board below, all pieces can be removed from the board. For example, the selected piece can be dragged one square down, then one square left, and finally it can be removed from the board by dragging it down:
You take alternate turns removing pieces from the board until all of them are removed. The score of each player is calculated by summing the values of the pieces he has removed. Each player follows an optimal strategy that maximizes the difference between his score and his opponent's score. You are the first to move.
You will be given a String board. Each element of board contains four integers separated by single spaces. The jth integer in the ith element of board represents the number written on the piece in the ith row and jth column of the grid. Return the maximum possible score difference between you and your friend, assuming both of you play optimally.