转角路径的乘积中最多能有几个尾随零

You are given a 2D integer array grid of size m x n, where each cell contains a positive integer.

A cornered path is defined as a set of adjacent cells with at most one turn. More specifically, the path should exclusively move either horizontally or vertically up to the turn (if there is one), without returning to a previously visited cell. After the turn, the path will then move exclusively in the alternate direction: move vertically if it moved horizontally, and vice versa, also without returning to a previously visited cell.

The product of a path is defined as the product of all the values in the path.

Return the maximum number of trailing zeros in the product of a cornered path found in grid.

Note:

• Horizontal movement means moving in either the left or right direction.
• Vertical movement means moving in either the up or down direction.

 

Example 1:

Input: grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]
Output: 3
Explanation: The grid on the left shows a valid cornered path.
It has a product of 15 * 20 * 6 * 1 * 10 = 18000 which has 3 trailing zeros.
It can be shown that this is the maximum trailing zeros in the product of a cornered path.

The grid in the middle is not a cornered path as it has more than one turn.
The grid on the right is not a cornered path as it requires a return to a previously visited cell.

Example 2:

Input: grid = [[4,3,2],[7,6,1],[8,8,8]]
Output: 0
Explanation: The grid is shown in the figure above.
There are no cornered paths in the grid that result in a product with a trailing zero.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= grid[i][j] <= 1000

题解通过预处理每个数字的2和5的因子个数，并利用这些预处理的数据来计算二维网格每个位置的累计因子数，最终以此来找出转角路径乘积中尾随零的最大数目。具体步骤为：1. 对所有可能的数字值从2到1000，计算并存储每个数字分解中2和5的个数。2. 为了有效计算乘积的尾随零数目，使用前缀和的方法存储网格中每一行从开始到当前列的2和5的因子的总数。3. 遍历网格的每一列，计算从当前列向左或向右拐弯时2和5的因子总数，使用上述前缀和加速这一计算。4. 从每个网格点考虑所有可能的转角路径（向上、向下、向左、向右），并更新尾随零的最大数目。这种方法有效地利用了动态规划的思想和前缀和技术，避免了重复计算。

O(m * n)

O(m * n)