分析
从最朴素的眼光来看就是要找到一个点的位置,让他能够搜索到最长的路径,如果说直接暴力搜索的话,是直接要对N*N的矩阵全部要进行深度搜索,这样的时间复杂度比较高。
让我们仔细思考朴素做法的过程,实际上在遍历每个点的时候就是把他当作起点的找最大长度,如果说我们的下一个点能够找到这个点,而这个点已经拥有了最大长度,我们就直接把这个经过的点的最长的距离加上就成为了我们当前搜索的点的最大距离。
我们就可以用一个f[i][j]来表示位于i,j处的点的最长的滑行距离。
从上下左右四个方向都可以滑行,所以我们只需要找到上下左右四个方向的最大距离,所以我们的状态转移方程为f[i][j]=min(f[i][j],dfs(a,b));
如果说我们的点已经具有了最长的搜索距离那么就只需要返回这个最长的距离就好了
代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/18/%E6%BB%91%E9%9B%AA/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!