leetcode 688. “马”在棋盘上的概率

题目描述：

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

思路分析：

思路1: 首先想到的是用dfs，但是这样会超时，最坏情况可能达到8的100次方。

思路2: 三维dp，dp[i][j][k]表示在点(i, j)上移动了k次后改点仍然位于棋盘上的概率。首先，初始条件dp[i][j][0]=1。接下来四层的循环，最外层为1到k次的移动，接下来是位置i,j的两重循环，最后是移动方向1到8的循环，dp[i][j][num] = sum(dp[i][j][num-1]*(1.0/8.0))，即当前点k次的概率为所有k-1次的概率之和。

代码：

 1 class Solution {
 2 public:
 3     double knightProbability(int N, int K, int r, int c) {
 4         if(K<=0)
 5             return 1.0;
 6         if(N<0 || r<0 || r>=N || c<0 || c>=N)
 7             return 0.0;
 8         double dp[26][26][101];
 9         int direction[][2] = {{-1, -2}, {1, -2}, {-1, 2}, {1, 2}, {-2, -1}, {-2, 1}, {2, -1}, {2, 1}};
10         for(int i=0; i<N; i++)
11             for(int j=0; j<N; j++)
12                 dp[i][j][0]=1;
13         for(int num=1; num<=K; num++)
14         {
15             for(int i=0; i<N; i++)
16             {
17                 for(int j=0; j<N; j++)
18                 {
19                     double tmp = 0;
20                     for(int l=0; l<8; l++)
21                     {
22                         int x = i+direction[l][0];
23                         int y = j+direction[l][1];
24                         if(x<0 || y<0 || x>=N || y>=N)
25                             continue;
26                         tmp += (1.0/8.0)*dp[x][y][num-1];
27                     }
28                     dp[i][j][num] = tmp;
29                 }
30             }
31         }
32         return dp[r][c][K];
33     }
34 };