- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我尝试了这个问题,但由于某种原因,结果不正确。给定一组字符串,找出迷宫中存在多少种可能的解决方案,其中字符串由一个“R”(老鼠)、一个“C”(奶酪)、多个“X”(无法通过的方 block )和“.”(可能的路径)组成。任务是找出老鼠到达奶酪时可以采取的可能路线数,而不会增加其路径上任何点与奶酪之间的(欧几里得)距离。我的代码看起来有什么问题吗?
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;
}
}
最佳答案
让我们从一个有用的观察开始:
[...] without ever increasing the (Euclidean) distance between itself and the cheese at any point on its path.
基本上,这意味着每当老鼠靠近奶酪时,它就永远不会回到更远的位置。
因此,假设老鼠 x 坐标为 3,奶酪 x 坐标为 5,则老鼠无法“向左走”(即 x = 2
),因为这会导致它比之前距离奶酪更远。
因此,简化问题的一个好方法是找到老鼠可以走的方向。在您的示例中,老鼠位于奶酪的左上方,因此它只能向下或向右移动,否则它会离奶酪更远。当老鼠x与奶酪x匹配时,它将无法再向右或向左移动,y也是如此。
使用您的代码,如果:
r[0] - c[0] = 0 // the rat cannot move on the x any more.
r[1] - c[1] = 0 // the rat cannot move on the y any more.
什么时候
r[0] - c[0] == 0 && r[1] - c[1] == 0
老鼠到达了奶酪!在这种情况下,我们可以增加计数器,因为找到了成功的路由。
现在让我们通过递归来实践这一点。从您发布的代码中,我们从给定的 c
(使用 findC(enc)
找到)和给定的 r
(使用 findR(enc)
找到)开始
因此递归方法如下所示:
private void findRoutesFrom(int[] r) {
// what directions can the rat go?
// if the cheese is on the right of the mouse, xDirection
// would be +1.
int xDirection = (int) Math.signum(c[0] - r[0]);
// if the cheese is below of the mouse, yDirection
// would be +1.
int yDirection = (int) Math.signum(c[1] - r[1]);
// Now, if xDirection is != 0 the rat can attempt to move
// in that direction, checking if there's not a block
if(xDirection != 0 && !isBlock(r[0] + xDirection, r[1])) {
// if it can move in that direction, then use recursion to
// find all the possible paths form the new position
findRoutesFrom(new int[]{r[0] + xDirection, r[1]});
}
// same goes for yDirection
if(yDirection != 0 && !isBlock(r[0], r[1] + yDirection)) {
findRoutesFrom(new int[]{r[0], r[1] + yDirection});
}
// if the rat reaches the cheese, increase the successful
// paths counter
if(xDirection == 0 && yDirection == 0) {
count++;
}
}
就是这样!由于 Eculedean 距离约束,检查方向是否为 != 0
就足够了,因为当方向为 false 时,老鼠就无法再沿该方向移动。
关于java - 在java中使用递归来解决迷宫问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38649044/
我正在编写一个具有以下签名的 Java 方法。 void Logger(Method method, Object[] args); 如果一个方法(例如 ABC() )调用此方法 Logger,它应该
我是 Java 新手。 我的问题是我的 Java 程序找不到我试图用作的图像文件一个 JButton。 (目前这段代码什么也没做,因为我只是得到了想要的外观第一的)。这是我的主课 代码: packag
好的,今天我在接受采访,我已经编写 Java 代码多年了。采访中说“Java 垃圾收集是一个棘手的问题,我有几个 friend 一直在努力弄清楚。你在这方面做得怎么样?”。她是想骗我吗?还是我的一生都
我的 friend 给了我一个谜语让我解开。它是这样的: There are 100 people. Each one of them, in his turn, does the following
如果我将使用 Java 5 代码的应用程序编译成字节码,生成的 .class 文件是否能够在 Java 1.4 下运行? 如果后者可以工作并且我正在尝试在我的 Java 1.4 应用程序中使用 Jav
有关于why Java doesn't support unsigned types的问题以及一些关于处理无符号类型的问题。我做了一些搜索,似乎 Scala 也不支持无符号数据类型。限制是Java和S
我只是想知道在一个 java 版本中生成的字节码是否可以在其他 java 版本上运行 最佳答案 通常,字节码无需修改即可在 较新 版本的 Java 上运行。它不会在旧版本上运行,除非您使用特殊参数 (
我有一个关于在命令提示符下执行 java 程序的基本问题。 在某些机器上我们需要指定 -cp 。 (类路径)同时执行java程序 (test为java文件名与.class文件存在于同一目录下) jav
我已经阅读 StackOverflow 有一段时间了,现在我才鼓起勇气提出问题。我今年 20 岁,目前在我的家乡(罗马尼亚克卢日-纳波卡)就读 IT 大学。足以介绍:D。 基本上,我有一家提供簿记应用
我有 public JSONObject parseXML(String xml) { JSONObject jsonObject = XML.toJSONObject(xml); r
我已经在 Java 中实现了带有动态类型的简单解释语言。不幸的是我遇到了以下问题。测试时如下代码: def main() { def ks = Map[[1, 2]].keySet()
一直提示输入 1 到 10 的数字 - 结果应将 st、rd、th 和 nd 添加到数字中。编写一个程序,提示用户输入 1 到 10 之间的任意整数,然后以序数形式显示该整数并附加后缀。 public
我有这个 DownloadFile.java 并按预期下载该文件: import java.io.*; import java.net.URL; public class DownloadFile {
我想在 GUI 上添加延迟。我放置了 2 个 for 循环,然后重新绘制了一个标签,但这 2 个 for 循环一个接一个地执行,并且标签被重新绘制到最后一个。 我能做什么? for(int i=0;
我正在对对象 Student 的列表项进行一些测试,但是我更喜欢在 java 类对象中创建硬编码列表,然后从那里提取数据,而不是连接到数据库并在结果集中选择记录。然而,自从我这样做以来已经很长时间了,
我知道对象创建分为三个部分: 声明 实例化 初始化 classA{} classB extends classA{} classA obj = new classB(1,1); 实例化 它必须使用
我有兴趣使用 GPRS 构建车辆跟踪系统。但是,我有一些问题要问以前做过此操作的人: GPRS 是最好的技术吗?人们意识到任何问题吗? 我计划使用 Java/Java EE - 有更好的技术吗? 如果
我可以通过递归方法反转数组,例如:数组={1,2,3,4,5} 数组结果={5,4,3,2,1}但我的结果是相同的数组,我不知道为什么,请帮助我。 public class Recursion { p
有这样的标准方式吗? 包括 Java源代码-测试代码- Ant 或 Maven联合单元持续集成(可能是巡航控制)ClearCase 版本控制工具部署到应用服务器 最后我希望有一个自动构建和集成环境。
我什至不知道这是否可能,我非常怀疑它是否可能,但如果可以,您能告诉我怎么做吗?我只是想知道如何从打印机打印一些文本。 有什么想法吗? 最佳答案 这里有更简单的事情。 import javax.swin
我是一名优秀的程序员,十分优秀!