Ritter bewegt sich auf ein Schachbrett für verschiedene Definitionen eines Ritterbewegung ⇐ Java

[Guest]

Ich versuche, Hackerrank -Problem Knightl auf einem Schachbrett zu lösen: < /p>

Kightl < /em> ist ein Schachstück, das sich in einem L bewegt Form. Wir definieren die möglichen Bewegungen von kightl (𝑎, 𝑏) als jede Bewegung von einer Position (𝑥 1 , 𝑦 1 ) zu einigen (𝑥 2 , 𝑦 2 ), die eine der folgenden erfüllen:

[*] 𝑥 2 = 𝑥 1 ± 𝑎
[*] 𝑦 2 = 𝑦 1 ± 𝑏
< /ul>
·. 𝑎, 𝑏) Paar, wobei 1 ≤ 𝑎, 𝑏

Was ist die minimale Anzahl von Bewegungen, die es für kightl < /em> erfordert (𝑎, 𝑏), um von Position (0,0) zur Position (𝑛 - 1, 𝑛 - 1) zu erreichen? Wenn es für den Ritter nicht möglich ist, dieses Ziel zu erreichen, ist die Antwort stattdessen -1. > Einschränkungen < /H3>

5 ≤ 𝑛 ≤ 25 < /li>
< /ul>
Probeeingang Probeneingang < /h3>
5 < /p>
Beispielausgabe < /h3>

Code: Select all

4  4  2  8
4  2  4  4
2  4 -1 -1
8  4 -1  1

Erläuterung
Das folgende Diagramm zeigt mögliche minimale Pfade für kightl (1,1), kightl (1,2) und kightl (1,3):
Ein minimaler Pfad für kightl (1,4 ) IS: < /p>
(0,0) → (1,4) → (2,0) → (3,4) → (4,0) → (0,1) → (4,2) → (0,3) → (4,4)
Wir haben dann [haben] 4 4 2 8 als unsere erste Ausgabezeile, weil Kightl (1,1) nahm 4 Moves, kightl (1,2) 4 Bewegungen, kightl (1,3) 2 Bewegungen und machte 2 Bewegungen und kightl (1,4) machte 8 Moves. Mein Code funktioniert, hat aber eine sehr hohe Komplexität. Dies ist mein Code: < /p>

Code: Select all

public class lknightmycode {

public static boolean canreach(int[][] board, int row, int col) {
if(row>=0 && col>=0 && row< board.length&&col< board.length&&board[row][col]==-1){
return true;
}
else return false;
}

public static int helper(int[][] board, int row, int col, int crow, int ccol, int steps) {
if (crow == board.length - 1 && ccol == board.length - 1){
return steps;}
if (canreach(board, crow, ccol)) {
board[crow][ccol] = 0;

int minSteps = Integer.MAX_VALUE;
int[] dr = {-row, -row, row, row,col, -col, col, -col};
int[] dc = {col, -col, col, -col,-row, -row, row, row};

for (int i = 0; i < 8; i++) {
int newRow = crow + dr[i];
int newCol = ccol + dc[i];

int currentSteps = helper(board, row, col, newRow, newCol, steps + 1);
if (currentSteps != -1) {
minSteps = Math.min(minSteps, currentSteps);
}
}
board[crow][ccol] = -1; // Reset the board position

return (minSteps == Integer.MAX_VALUE) ? -1 : minSteps;
}

return -1;
}
public static int[][] knightlOnAChessboard(int n) {
int[][] board = new int[n][n];
int[][] Result = new int[n - 1][n - 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = -1;
}}
for (int i = 0; i < n-1; i++) {
for (int j = 0; j