A chess rook can move horizontally or vertically to any square in the same row or in the same column of a chessboard (8 by 8). You are asked to find the number of shortest paths by which a rook can move from one corner of a chessboard to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the first and the last squares. Solve the problem by a dynamic programming algorithm. Write down your recurrence relation and initial condition. Briefly explain your solution.