1
Ich habe dieses Problem versucht und aus irgendeinem Grund ist es nicht richtig. Bei einem Array von Strings, finde heraus, wie viele mögliche Lösungen für das Labyrinth existieren, wo die Strings aus einem "R" (der Ratte), einem "C" (dem Käse), mehreren "X's" (Blöcke, die nicht passieren können) besteht. und "." (mögliche Wege). Die Aufgabe ist es, die Anzahl der möglichen Wege zu finden, die die Ratte nehmen kann, um an den Käse zu kommen, ohne jemals die (euklidische) Distanz zwischen sich und dem Käse zu erhöhen. Was mit meinem Code falsch aussiehtVerwenden von Rekursion zum Lösen eines Maze in Java
public class RatRoute {
private static String[] enc;
private static int count;
private static int[] r;
private static int[] c;
// Test the program
public static void main(String[] args) {
String[] test = {
".R...",
"..X..",
"....X",
"X.X.X",
"...C."};
int num1 = numRoutes(test);
System.out.println(num1);
}
// Set variables, and call recursive function
public static int numRoutes(String[] enc) {
RatRoute.enc = enc;
r = findR(enc);
c = findC(enc);
recursiveHelper(r[0], r[1]);
return count;
}
// Recursive
public static void recursiveHelper(int x, int y) {
/*System.out.println();
System.out.println();
for (int k = 0; k < enc.length; k++) {
System.out.println(enc[k]);
}*/
if(isBlock(x,y)) {
return;
} else if (isBigger(x,y)) {
return;
} else if (isCheese(x, y)) {
count++;
//System.out.println("Found the Cheese! Path number: " + count);
//System.out.println();
return;
}
enc[x] = currentPath(x,y);
recursiveHelper(x + 1, y);
recursiveHelper(x, y + 1);
recursiveHelper(x, y - 1);
recursiveHelper(x - 1, y);
enc[x] = returnPath(x,y);
}
// Change the most recently traveled coordinates into a block
public static String currentPath(int x, int y) {
char[] Chars = enc[x].toCharArray();
Chars[y] = 'X';
String newString = String.valueOf(Chars);
return newString;
}
// Turn path already traveled from blocks back into a usable path to travel (undo the currentPath method)
public static String returnPath(int x, int y) {
char[] Chars = enc[x].toCharArray();
Chars[y] = '.';
String newString = String.valueOf(Chars);
return newString;
}
// Check if the next movement is into the cheese
public static boolean isCheese(int x, int y) {
if (enc[x].charAt(y) == 'C') {
return true;
} else {
return false;
}
}
// Check if the next movement is into a block, or outside the given array
public static boolean isBlock(int x, int y) {
if (x == -1 || y == -1
|| x >= enc.length || y >= enc[x].length()) {
return true;
} else if (enc[x].charAt(y) == 'X') {
//System.out.println(x + "," + y);
return true;
} else {
return false;
}
}
// See if the distance between the rat and the cheese has gotten larger or smaller
public static boolean isBigger(int x, int y) {
double rx = r[0]; double ry = r[1];
double cx = c[0]; double cy = c[1];
double originalDist = Math.sqrt(Math.pow(rx-cx, 2) + Math.pow(ry-cy, 2));
double newDist = Math.sqrt(Math.pow(x-cx, 2) + Math.pow(y-cy, 2));
//System.out.println("Orginal Distance: " + originalDist);
//System.out.println("New Distance: " + newDist);
if (newDist > originalDist) {
return true;
} else {
return false;
}
}
// Find the variables for the original position of the rat
public static int[] findR(String[] enc) {
for (int i = 0; i < enc.length; i++) {
for (int j = 0; j < enc[i].length(); j++) {
if (enc[i].charAt(j) == 'R') {
int[] coordinates = {i, j};
//System.out.println(coordinates[0] + "," + coordinates[1]);
return coordinates;
} else {
}
}
}
int[] other = {-1, -1};
return other;
}
// Find the variables for the original position of the rat
public static int[] findC(String[] enc) {
for (int i = 0; i < enc.length; i++) {
for (int j = 0; j < enc[i].length(); j++) {
if (enc[i].charAt(j) == 'C') {
int[] coordinates = {i, j};
//System.out.println(coordinates[0] + "," + coordinates[1]);
return coordinates;
} else {
}
}
}
int[] other = {-1, -1};
return other;
}
}
Die Antwort auf das bestimmte Beispiel im Code wäre 3, wenn das hilft. – Steve