|
1 | 1 | packageg3201_3300.s3283_maximum_number_of_moves_to_kill_all_pawns;
|
2 | 2 |
|
3 | 3 | // #Hard #Array #Math #Breadth_First_Search #Bit_Manipulation #Bitmask #Game_Theory
|
4 |
| -// #2024_09_09_Time_250_ms_(98.43%)_Space_50.1_MB_(66.27%) |
| 4 | +// #2025_03_22_Time_126_ms_(100.00%)_Space_48.23_MB_(72.09%) |
5 | 5 |
|
6 |
| -importjava.util.LinkedList; |
| 6 | +importjava.util.ArrayDeque; |
7 | 7 | importjava.util.Queue;
|
8 | 8 |
|
9 | 9 | publicclassSolution {
|
10 |
| -privatestaticfinalint[][]KNIGHT_MOVES = { |
11 |
| - {-2, -1}, {-2,1}, {-1, -2}, {-1,2}, |
12 |
| - {1, -2}, {1,2}, {2, -1}, {2,1} |
| 10 | +privatestaticfinalint[][]DIRECTIONS = { |
| 11 | + {2,1}, {1,2}, {-1,2}, {-2,1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1} |
13 | 12 | };
|
14 |
| -privateint[][]distances; |
15 |
| -privateInteger[][]memo; |
16 | 13 |
|
17 |
| -publicintmaxMoves(intkx,intky,int[][]positions) { |
| 14 | +privatevoidinitializePositions(int[][]positions,int[][]pos,intkx,intky) { |
18 | 15 | intn =positions.length;
|
19 |
| -distances =newint[n +1][n +1]; |
20 |
| -memo =newInteger[n +1][1 <<n]; |
21 |
| -// Calculate distances between all pairs of positions (including knight's initial position) |
22 | 16 | for (inti =0;i <n;i++) {
|
23 |
| -distances[n][i] =calculateMoves(kx,ky,positions[i][0],positions[i][1]); |
24 |
| -for (intj =i +1;j <n;j++) { |
25 |
| -intdist = |
26 |
| -calculateMoves( |
27 |
| -positions[i][0],positions[i][1],positions[j][0],positions[j][1]); |
28 |
| -distances[i][j] =distances[j][i] =dist; |
29 |
| - } |
| 17 | +intx =positions[i][0]; |
| 18 | +inty =positions[i][1]; |
| 19 | +pos[x][y] =i; |
30 | 20 | }
|
31 |
| -returnminimax(n, (1 <<n) -1,true); |
| 21 | +pos[kx][ky] =n; |
32 | 22 | }
|
33 | 23 |
|
34 |
| -privateintminimax(intlastPos,intremainingPawns,booleanisAlice) { |
35 |
| -if (remainingPawns ==0) { |
36 |
| -return0; |
37 |
| - } |
38 |
| -if (memo[lastPos][remainingPawns] !=null) { |
39 |
| -returnmemo[lastPos][remainingPawns]; |
40 |
| - } |
41 |
| -intresult =isAlice ?0 :Integer.MAX_VALUE; |
42 |
| -for (inti =0;i <distances.length -1;i++) { |
43 |
| -if ((remainingPawns & (1 <<i)) !=0) { |
44 |
| -intnewRemainingPawns =remainingPawns & ~(1 <<i); |
45 |
| -intmoveValue =distances[lastPos][i] +minimax(i,newRemainingPawns, !isAlice); |
46 |
| - |
47 |
| -if (isAlice) { |
48 |
| -result =Math.max(result,moveValue); |
49 |
| - }else { |
50 |
| -result =Math.min(result,moveValue); |
| 24 | +privatevoidcalculateDistances(int[][]positions,int[][]pos,int[][]distances) { |
| 25 | +intn =positions.length; |
| 26 | +for (inti =0;i <n;i++) { |
| 27 | +intcount =n -i; |
| 28 | +boolean[][]visited =newboolean[50][50]; |
| 29 | +visited[positions[i][0]][positions[i][1]] =true; |
| 30 | +Queue<int[]>que =newArrayDeque<>(); |
| 31 | +que.offer(newint[] {positions[i][0],positions[i][1]}); |
| 32 | +intsteps =1; |
| 33 | +while (!que.isEmpty() &&count >0) { |
| 34 | +intsize =que.size(); |
| 35 | +while (size-- >0) { |
| 36 | +int[]cur =que.poll(); |
| 37 | +intx =cur[0]; |
| 38 | +inty =cur[1]; |
| 39 | +for (int[]d :DIRECTIONS) { |
| 40 | +intnx =x +d[0]; |
| 41 | +intny =y +d[1]; |
| 42 | +if (0 <=nx &&nx <50 &&0 <=ny &&ny <50 && !visited[nx][ny]) { |
| 43 | +que.offer(newint[] {nx,ny}); |
| 44 | +visited[nx][ny] =true; |
| 45 | +intj =pos[nx][ny]; |
| 46 | +if (j >i) { |
| 47 | +distances[i][j] =distances[j][i] =steps; |
| 48 | +if (--count ==0) { |
| 49 | +break; |
| 50 | + } |
| 51 | + } |
| 52 | + } |
| 53 | + } |
| 54 | +if (count ==0) { |
| 55 | +break; |
| 56 | + } |
51 | 57 | }
|
| 58 | +steps++; |
52 | 59 | }
|
53 | 60 | }
|
54 |
| -memo[lastPos][remainingPawns] =result; |
55 |
| -returnresult; |
56 | 61 | }
|
57 | 62 |
|
58 |
| -privateintcalculateMoves(intx1,inty1,intx2,inty2) { |
59 |
| -if (x1 ==x2 &&y1 ==y2) { |
60 |
| -return0; |
61 |
| - } |
62 |
| -boolean[][]visited =newboolean[50][50]; |
63 |
| -Queue<int[]>queue =newLinkedList<>(); |
64 |
| -queue.offer(newint[] {x1,y1,0}); |
65 |
| -visited[x1][y1] =true; |
66 |
| -while (!queue.isEmpty()) { |
67 |
| -int[]current =queue.poll(); |
68 |
| -intx =current[0]; |
69 |
| -inty =current[1]; |
70 |
| -intmoves =current[2]; |
71 |
| -for (int[]move :KNIGHT_MOVES) { |
72 |
| -intnx =x +move[0]; |
73 |
| -intny =y +move[1]; |
74 |
| -if (nx ==x2 &&ny ==y2) { |
75 |
| -returnmoves +1; |
76 |
| - } |
77 |
| -if (nx >=0 &&nx <50 &&ny >=0 &&ny <50 && !visited[nx][ny]) { |
78 |
| -queue.offer(newint[] {nx,ny,moves +1}); |
79 |
| -visited[nx][ny] =true; |
| 63 | +privateintcalculateDP(intn,int[][]distances) { |
| 64 | +intm = (1 <<n) -1; |
| 65 | +int[][]dp =newint[1 <<n][n +1]; |
| 66 | +for (intmask =1;mask < (1 <<n);mask++) { |
| 67 | +booleanisEven = (Integer.bitCount(m ^mask)) %2 ==0; |
| 68 | +for (inti =0;i <=n;i++) { |
| 69 | +intresult =0; |
| 70 | +if (isEven) { |
| 71 | +for (intj =0;j <n;j++) { |
| 72 | +if ((mask & (1 <<j)) >0) { |
| 73 | +result =Math.max(result,dp[mask ^ (1 <<j)][j] +distances[i][j]); |
| 74 | + } |
| 75 | + } |
| 76 | + }else { |
| 77 | +result =Integer.MAX_VALUE; |
| 78 | +for (intj =0;j <n;j++) { |
| 79 | +if ((mask & (1 <<j)) >0) { |
| 80 | +result =Math.min(result,dp[mask ^ (1 <<j)][j] +distances[i][j]); |
| 81 | + } |
| 82 | + } |
80 | 83 | }
|
| 84 | +dp[mask][i] =result; |
81 | 85 | }
|
82 | 86 | }
|
83 |
| -// Should never reach here if input is valid |
84 |
| -return -1; |
| 87 | +returndp[m][n]; |
| 88 | + } |
| 89 | + |
| 90 | +publicintmaxMoves(intkx,intky,int[][]positions) { |
| 91 | +intn =positions.length; |
| 92 | +int[][]pos =newint[50][50]; |
| 93 | +initializePositions(positions,pos,kx,ky); |
| 94 | +int[][]distances =newint[n +1][n +1]; |
| 95 | +calculateDistances(positions,pos,distances); |
| 96 | +returncalculateDP(n,distances); |
85 | 97 | }
|
86 | 98 | }
|