|
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 | } |