Facebook engineers love playing chess. They also like to play other games on the chessboard. Today, they were wondering how many cells a knight would visit on the chessboard if it followed some predefined algorithm.
You are given a String[] **board** describing a standard 8x8 chessboard, where the c-th character of the r-th element corresponds to the cell in row r, column c. Some cells are blocked and cannot be jumped into. These will be represented with a '*'. All other cells are marked with a '.', except for the starting position of the knight, which is marked with a 'K'.
A valid jump for a knight consists of shifting one square along one axis and two squares along the other axis. A cell is "accessible" if it is not blocked and it has not been visited by the knight before. The starting position of the knight is considered to be visited, and each time the knight jumps into a new cell, that cell becomes visited. The accessibility number of a cell is the number of accessible cells that the knight can make a valid jump to from that cell. Note that accessibility numbers of cells may change as the knight moves through the board and visits more cells.
The knight will use the following simple algorithm to traverse the board. On each move, it will make a valid jump into the accessible cell with the lowest accessibility number. In case of a tie, it will choose the one with the lowest row number, and if there is still a tie, it will choose the one among them with the lowest column number. The knight will stop moving when it can no longer make a valid jump into an accessible cell.
Return the number of cells that the knight will visit (including the starting cell). |