1594. 矩阵的最大非负积-深度优先遍历

1594. 矩阵的最大非负积-深度优先遍历

给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为负数，则返回 -1 。

注意，取余是在得到最大积之后执行的。

示例 1：

输入：grid = [[-1,-2,-3],
[-2,-3,-3],
[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1

示例 2：

输入：grid = [[1,-2,1],
[1,-2,1],
[3,-4,1]]
输出：8
解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)

示例 3：

输入：grid = [[1, 3],
[0,-4]]
输出：0
解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)

示例 4：

输入：grid = [[ 1, 4,4,0],
[-2, 0,0,1],
[ 1,-1,1,1]]
输出：2
解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)

这一题，采用深度优先遍历是可以的，最好加个记忆化搜索，我这里没加，解题代码如下：

int re;
 void dfs(int **grid,int m,int n,int x_now,int y_now,long long val,int **r){
     int direction[4][2]={{0,1},{1,0}};
   //  printf("%d %d %d |",x_now,y_now,val);
     if(x_now==m-1&&y_now==n-1&&val>=0){
         re=fmax(re,val);

     }
   
      
     for(int i=0;i<2;i++){
         int x_next=x_now+direction[i][0];
         int y_next=y_now+direction[i][1];
         if(x_next>=0&&x_next<m&&y_next>=0&&y_next<n){
        //     printf("%d %d ",x_next,y_next);
              
                 dfs(grid,m,n,x_next,y_next,val*grid[x_next][y_next],r);

         }
     }

 }




int maxProductPath(int** grid, int gridSize, int* gridColSize){
    int n=gridColSize[0],m=gridSize;
     int **r=(int **)malloc(sizeof(int *)*m);
   re=-1;

    
    for(int i=0;i<m;i++){
       
        r[i]=(int *)malloc(sizeof(int )*n);
        for(int j=0;j<n;j++){
            r[i][j]=0;
        }
    }
    long long a=grid[0][0];
    dfs(grid,m,n,0,0,a,r);
    return re%1000000007;

}