|
1 | 1 | packageg2601_2700.s2684_maximum_number_of_moves_in_a_grid; |
2 | 2 |
|
3 | | -// #Medium #Array #Dynamic_Programming #Matrix #2023_09_12_Time_4_ms_(97.95%)_Space_54.4_MB_(68.34%) |
| 3 | +// #Medium #Array #Dynamic_Programming #Matrix #2023_09_19_Time_3_ms_(99.53%)_Space_55.4_MB_(15.49%) |
| 4 | + |
| 5 | +importjava.util.Arrays; |
4 | 6 |
|
5 | 7 | publicclassSolution { |
6 | 8 | publicintmaxMoves(int[][]grid) { |
7 | | -intm =Integer.MIN_VALUE; |
8 | | -int[][]vis =newint[grid.length][grid[0].length]; |
9 | | -for (inti =0;i <grid.length;i++) { |
10 | | -m =Math.max(m,mov(i,0,grid,Integer.MIN_VALUE,vis)); |
11 | | - } |
12 | | -returnm -1; |
13 | | - } |
14 | | - |
15 | | -privateintmov(inti,intj,int[][]g,intp,int[][]vis) { |
16 | | -if (i <0 ||j <0 ||i >=g.length ||j >=g[0].length ||g[i][j] <=p ||vis[i][j] ==1) { |
17 | | -return0; |
| 9 | +inth =grid.length; |
| 10 | +boolean[]dp1 =newboolean[h]; |
| 11 | +boolean[]dp2 =newboolean[h]; |
| 12 | +intrtn =0; |
| 13 | +Arrays.fill(dp1,true); |
| 14 | +for (intcol =1;col <grid[0].length;col++) { |
| 15 | +booleanf =false; |
| 16 | +for (introw =0;row <h;row++) { |
| 17 | +intpr =row -1; |
| 18 | +intnr =row +1; |
| 19 | +dp2[row] =false; |
| 20 | +if (pr >=0 &&dp1[pr] &&grid[pr][col -1] <grid[row][col]) { |
| 21 | +dp2[row] =true; |
| 22 | +f =true; |
| 23 | + } |
| 24 | +if (nr <h &&dp1[nr] &&grid[nr][col -1] <grid[row][col]) { |
| 25 | +dp2[row] =true; |
| 26 | +f =true; |
| 27 | + } |
| 28 | +if (dp1[row] &&grid[row][col -1] <grid[row][col]) { |
| 29 | +dp2[row] =true; |
| 30 | +f =true; |
| 31 | + } |
| 32 | + } |
| 33 | +boolean[]t =dp1; |
| 34 | +dp1 =dp2; |
| 35 | +dp2 =t; |
| 36 | +if (f) { |
| 37 | +rtn++; |
| 38 | + }else { |
| 39 | +break; |
| 40 | + } |
18 | 41 | } |
19 | | -vis[i][j] =1; |
20 | | -intur =1 +mov(i -1,j +1,g,g[i][j],vis); |
21 | | -intdr =1 +mov(i +1,j +1,g,g[i][j],vis); |
22 | | -intr =1 +mov(i,j +1,g,g[i][j],vis); |
23 | | -returnMath.max(ur,Math.max(dr,r)); |
| 42 | +returnrtn; |
24 | 43 | } |
25 | 44 | } |