https://leetcode.com/problems/knight-probability-in-chessboard/description/
688. Knight Probability in Chessboard
给你一个数字 n 表示一个 n x n 的西洋棋盘，他的座标用 0-index 来表示
我们把一个骑士放在棋盘的 [row, column] 位置，骑士可以往八个方向移动
https://assets.leetcode.com/uploads/2018/10/12/knight.png
棋子在移动 k 步时停下（可以走出棋盘外），求出骑士恰好移动 k 步之后，他仍留
在棋盘上的机率是多少。
Example 1:
Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight
on the board.
From each of those positions, there are also two moves that will keep the
knight on the board.
The total probability the knight stays on the board is 0.0625.
Example 2:
Input: n = 1, k = 0, row = 0, column = 0
Output: 1.00000
方法一：DFS（TLE）
1.一个棋子可以走 k 步，每次有八种走法，所以共有 8^k 种走法，我们只要求出
哪些走法可以停在棋盘上并放在分子即可。
2.用DFS模拟棋子的所有走法，当恰好走完 k 步时没越界， res 递增。
3.答案为 res / 所有走法。
Java Code：