提高Java递归迷宫求解器的效率
提高Java递归迷宫求解器的效率
提问于 2018-09-27 08:26:52
更新
通过将线程大小增加到几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迷宫的输出示例
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52527730
复制相关文章
相似问题