0576. Out of Boundary Paths =========================== 题目信息 -------- :题号: 0576 :难度: Medium :主题: 网格移动、四方向、至多步数、越界路径计数 :原题: `LeetCode 0576 `_ :重点: 起点在网格内、每步上下左右移动、在至多 maxMove 步内首次越界即形成一条路径、答案取模 题目重述 -------- 有一个 ``m × n`` 网格,球从有效坐标 ``[startRow, startColumn]`` 开始。每一步可以向上、下、左或右移动一格。统计在至多 ``maxMove`` 步内把球移出网格边界的不同移动序列数量。 一旦某一步使球越界,该路径立即完成,不再继续移动。返回路径数量对 ``1,000,000,007`` 取模后的结果。若 ``maxMove = 0``,球无法移动出界,答案为 ``0``。 自建示例 -------- 狭长网格中的两阶段出界: .. code-block:: text 输入:m = 1,n = 2,maxMove = 2,startRow = 0,startColumn = 0 输出:6 解释:第一步向上、下、左共有 3 条路径直接出界;第一步向右后,第二步向上、下、右又有 3 条路径出界,共 6 条。 没有移动机会: .. code-block:: text 输入:m = 3,n = 3,maxMove = 0,startRow = 1,startColumn = 1 输出:0 解释:不能执行任何移动,因此无法离开网格。 按步数滚动统计仍在网格内的路径 ------------------------------ ``dp[row][column]`` 表示完成当前步数后仍位于该格的路径数。每次从格子向四个方向转移:若目标越界,就把该路径数加入答案;否则累加到下一层。越界路径不再进入下一层,正好实现“首次越界即结束”。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { const int mod = 1000000007; std::vector> current( m, std::vector(n, 0)); current[startRow][startColumn] = 1; const int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; long long answer = 0; for (int step = 0; step < maxMove; ++step) { std::vector> next( m, std::vector(n, 0)); for (int row = 0; row < m; ++row) { for (int column = 0; column < n; ++column) { int ways = current[row][column]; if (ways == 0) continue; for (const auto& direction : directions) { int nextRow = row + direction[0]; int nextColumn = column + direction[1]; if (nextRow < 0 || nextRow >= m || nextColumn < 0 || nextColumn >= n) { answer = (answer + ways) % mod; } else { next[nextRow][nextColumn] = (next[nextRow][nextColumn] + ways) % mod; } } } } current.swap(next); } return static_cast(answer); } }; 代码分析 -------- 每层只保存尚未出界的路径,所有出界转移立即计数并丢弃;因此每条移动序列在第一次出界的步数被计数一次。时间复杂度为 ``O(maxMove * m * n)``,滚动数组空间复杂度为 ``O(mn)``。