更新
通过将线程大小增加到几by,我能够让我的算法工作,并能够在一两秒内解决1803x1803的迷宫。
---------------
我昨天开始用Java自学递归。我创建了一个算法,可以拍摄迷宫的照片并解决它。然而,当我做大于200x200px的迷宫时,我得到了堆栈溢出的答案,因为我认为这个算法的堆栈太长了。我如何改进这个算法,以便我可以输入可能高达1000x1000的图像?
另外,你能告诉我我目前使用的是哪种算法吗?我相信这不是DFS,但我不确定。
请解释为什么你的解决方案更有效,以及它使用的想法。
这是解决问题的主类
public class BlackWhiteSolver {
static int[][] solutionSet = new int[203][203];
static int width, height;
static String originalImage;
static int correctX, correctY;
public static void convert() {
try {
BufferedImage original = ImageIO.read(new File(originalImage));
int red;
int threshold = 2;
width = original.getWidth();
height = original.getHeight();
for(int i=0; i<original.getWidth(); i++) {
for(int j=0; j<original.getHeight(); j++) {
red = new Color(original.getRGB(i, j)).getRed();
// 1 = white, 0 = black, 9 = tried, 5 = solved
if(red > threshold) { solutionSet[i][j] = 1; }
else { solutionSet[i][j] = 0; }
}
}
} catch (IOException e) {e.printStackTrace();}
}
public BlackWhiteSolver(int solvedX, int solvedY, String pic) {
correctX = solvedX;
correctY = solvedY;
originalImage = pic;
}
public boolean solve (int row, int column) {
boolean completed = false;
if (validPoint(row, column)) {
solutionSet[row][column] = 9;
if (row == correctX && column == correctY) {
completed = true;
} else {
completed = solve (row+1, column);
if (!completed) {
completed = solve (row, column+1);
}
if (!completed) {
completed = solve (row-1, column);
}
if (!completed) {
completed = solve (row, column-1);
}
}
if (completed) {
solutionSet[row][column] = 5;
}
}
return completed;
}
private boolean validPoint (int row, int column) {
boolean isValid = false;
if (row < height-1 && column < width-1 && row >= 1 && column >= 1 ) {
if (solutionSet[row][column] == 1) {
isValid = true;
}
}
return isValid;
}
public static void solvedFile() {
BufferedImage binarized = new BufferedImage(width, height,BufferedImage.TYPE_3BYTE_BGR);
int newPixel = 0;
int rgb = new Color(255, 0, 0).getRGB();
for(int i=0; i<width; i++){
for(int j=0; j<height; j++)
{
if (solutionSet[i][j] == 0) {
newPixel = 0;
newPixel = colorToRGB(1, newPixel, newPixel, newPixel);
} else if (solutionSet[i][j] == 1 || solutionSet[i][j] == 9) {
newPixel = 255;
newPixel = colorToRGB(1, newPixel, newPixel, newPixel);
} else if (solutionSet[i][j] == 5) {
newPixel = 16711680;
}
binarized.setRGB(i, j, newPixel);
}
}
try { ImageIO.write(binarized, "gif",new File("maze-complete") );} catch (IOException e) {e.printStackTrace();}
}
private static int colorToRGB(int alpha, int red, int green, int blue) {
int newPixel = 0;
newPixel += alpha;
newPixel = newPixel << 8;
newPixel += red; newPixel = newPixel << 8;
newPixel += green; newPixel = newPixel << 8;
newPixel += blue;
return newPixel;
}
}
这是运行迷宫的类
public class BlackWhiteInterface
{
public static void main (String[] args) {
BlackWhiteSolver puzzle = new BlackWhiteSolver(60, 202, "maze-4.gif");
System.out.println();
puzzle.convert();
if (puzzle.solve(0,34)) {
System.out.println("completed");
puzzle.solvedFile();
} else {
System.out.println("not possible");
}
}
}
生成具有起点和终点的正确迷宫
public class MazeBuilder {
static String start = "left";
static String end = "down";
public static void main(String[] args)
{
try
{
BufferedImage original = ImageIO.read(new File("mazeInput1.gif"));
BufferedImage binarized = new BufferedImage(original.getWidth(), original.getHeight(),BufferedImage.TYPE_BYTE_BINARY);
int red;
int redRightPixel;
int redUpPixel;
int newPixel;
int threshold = 2;
for(int i=0; i<original.getWidth(); i++)
{
for(int j=0; j<original.getHeight(); j++)
{
red = new Color(original.getRGB(i, j)).getRed();
int alpha = new Color(original.getRGB(i, j)).getAlpha();
if(red > threshold) { newPixel = 255; }
else { newPixel = 0; }
if (i == 0 || j == 0 || i == original.getWidth()-1 || j == original.getHeight() - 1){
newPixel = 0;
if (end == "left") {
} else if (end == "right") {
} else if (end == "up") {
} else if (end == "down") {
}
/*if (i == 1 || j == 1 || i == original.getWidth()-2 || j == original.getHeight() - 2 && red > 2) {
System.out.println("Start Point: (" + i + ", " + j + ")");
}
if (i == 0 && j > 0 && j < original.getHeight()-1) {
redRightPixel = new Color(original.getRGB(i+1, j)).getRed();
if (i == 0 && redRightPixel > 2) {
System.out.println("Start Point: (" + i + ", " + j + ")");
newPixel = 255;
}
}*/
/*if (j == original.getHeight()-1 && i > 0 && i < original.getWidth()-1) {
redUpPixel = new Color(original.getRGB(i, j-1)).getRed();
if (redUpPixel > 2) {
System.out.println("End Point: (" + i + ", " + j + ")");
newPixel = 255;
}
}*/
}
if (start == "left") {
if (i == 1 && j != 0 && j != original.getHeight()-1 && red > 2) {
System.out.println("Start Point: (" + i + ", " + j + ")");
}
} else if (start == "right") {
if (i == original.getHeight()-2 && j != 0 && j != original.getHeight()-1 && red > threshold) {
System.out.println("Start Point: (" + i + ", " + j + ")");
}
} else if (start == "up") {
if (j == 1 && i != 0 && i != original.getWidth()-1 && red > threshold) {
System.out.println("Start Point: (" + i + ", " + j + ")");
}
} else if (start == "down") {
if (j == original.getHeight()-2 && i != 0 && i != original.getWidth()-1 && red > threshold) {
System.out.println("Start Point: (" + i + ", " + j + ")");
}
}
if (end == "left") {
if (i == 1 && j != 0 && j != original.getHeight()-1 && red > 2) {
System.out.println("End Point: (" + i + ", " + j + ")");
}
} else if (end == "right") {
if (i == original.getHeight()-2 && j != 0 && j != original.getHeight()-1 && red > threshold) {
System.out.println("End Point: (" + i + ", " + j + ")");
}
} else if (end == "up") {
if (j == 1 && i != 0 && i != original.getWidth()-1 && red > threshold) {
System.out.println("End Point: (" + i + ", " + j + ")");
}
} else if (end == "down") {
if (j == original.getHeight()-2 && i != 0 && i != original.getWidth()-1 && red > threshold) {
System.out.println("End Point: (" + i + ", " + j + ")");
}
}
newPixel = colorToRGB(alpha, newPixel, newPixel, newPixel);
binarized.setRGB(i, j, newPixel);
}
}
ImageIO.write(binarized, "gif",new File("maze-4") );
}
catch (IOException e)
{
e.printStackTrace();
}
}
private static int colorToRGB(int alpha, int red, int green, int blue) {
int newPixel = 0;
newPixel += alpha;
newPixel = newPixel << 8;
newPixel += red; newPixel = newPixel << 8;
newPixel += green; newPixel = newPixel << 8;
newPixel += blue;
return newPixel;
}
}
203 x 203迷宫的输出示例
发布于 2018-09-27 08:41:07
一种简单的方法是不使用递归将到目前为止遵循的路径存储在堆栈中,这种方法的效率只略高一点。相反,将您到目前为止所遵循的路径存储在java.util.BitSet
中(将每个路径像素存储在BitSet
的元素y*width + x
中),或者您可以简单地使用已着色的图片的红色区域来存储路径。
这避免了堆栈溢出。
基本算法是从起点开始,在四个基本方向中的一个方向上进行,除非你已经访问过那个方向(要么尝试它并发现它是死胡同,要么从那个方向到达这里)。当你朝一个方向走时,你会在那里做同样的事情。这是一个简单的非递归循环。
当你走进死胡同时,你可以通过检查所有四个方向来找出你最初是如何到达那里的,看看这条路是从哪里来的。你把你所站的地方的红色去掉,然后回到你来的方向。如果在任何方向上都没有红色路径,那么你又回到了起点,你已经尝试了所有的方法,所以没有迷宫的解决方案。
当你回溯时,你会尝试下一个你还没有尝试过的方向,直到所有的方向都是死胡同。
如果你到达了终点,你就完了。
这里有一些伪代码,它们通常不能处理循环(在“圆”中的路径),效率非常低(例如,它应该使用BitSet
而不是boolean[][]
),这可能有一些but,但它给出了一般的想法:
public class MazeSolver {
private static enum Direction { UP, RIGHT, DOWN, LEFT }
// Return array's element is true if that's part of the path
public static boolean[][] solve(final boolean[][] mazeWallHere,
int x, int y,
final int endX, final int endY) {
final int width = mazeWallHere.length;
final int height = mazeWallHere[0].length;
final boolean[][] path = new boolean[width][height];
Direction nextDirection = Direction.UP;
boolean backtrack = false;
while (true) {
// If this spot is a dead end in all new directions, head back
if (backtrack) {
backtrack = false;
// Unmark where we are
path[x][y] = false;
// Find where we came from and what direction we took to get here
// Then switch to the next direction
// If all directions have been tried, backtrack again
// If we can't backtrack, return null because there's no solution
// If we went up to get here, go back down and try going right.
if (y != 0 && path[x][y - 1]) {
y--;
nextDirection = Direction.RIGHT;
continue;
}
// If we went right to get here, go back left and try going down.
else if (x != 0 && path[x - 1][y]) {
x--;
nextDirection = Direction.DOWN;
continue;
}
// If we went down to get here, go back up and try going left.
else if (y < height && path[x][y + 1]) {
y++;
nextDirection = Direction.LEFT;
continue;
}
// If we went left to get here, go back right and backtrack again.
else if (x < width && path[x + 1][y]) {
x++;
backtrack = true;
continue;
}
// If we didn't come from anywhere, we're at the starting point
// All possible paths are dead ends
else return null;
}
// Mark where we are
path[x][y] = true;
// If we've solved it, return the solution
if (x == endX && y == endY) return path;
// Move unless we:
// * hit the edge of the maze
// * it's the direction we originally got here from
// * hit a wall
// If we can't go a certain direction, try the next direction
// If we're out of directions to try, backtrack
switch (nextDirection) {
case UP: if (y == height
|| path[x][y + 1]
|| mazeWallHere[x][y + 1]) {
nextDirection = Direction.RIGHT;
continue;
}
else y++;
break;
case RIGHT: if (x == width
|| path[x + 1][y]
|| mazeWallHere[x + 1][y]) {
nextDirection = Direction.DOWN;
continue;
}
else x++;
break;
case DOWN: if (y == 0
|| path[x][y - 1]
|| mazeWallHere[x][y - 1]) {
nextDirection = Direction.LEFT;
continue;
}
else y--;
break;
case LEFT: if (x == 0
|| path[x - 1][y]
|| mazeWallHere[x - 1][y]) {
backtrack = true;
continue;
}
else x--;
break;
}
}
}
}
如果您想正确地处理周期,请将path
设置为int[][]
,并存储移动编号而不是true,这样您就可以知道哪条路径更旧。
https://stackoverflow.com/questions/52527730
复制相似问题