在 java 中使用回溯法解决迷宫问题

Question

我写了 java 代码，但它没有提供任何 output.Could 任何人帮助我 solution.thank you.I 提供了输入和输出。

这是代码-

输入- 5 4 OXOO OOX OOXO XOOO XXOO

输出- 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1

import java.util.*;

public class ratMaze {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        char[][] ch = new char[N][M];
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                ch[i][j]=sc.next().charAt(0);
            }
        }
        int[][] visited = new int[N][M];
        boolean res=ratmaze(ch,0,0,visited);
        if(res)
            print(visited,N,M);
        else
            System.out.print("-1");

    }

    private static boolean ratmaze(char[][]ch,int row,int col,int[][] visited)
    {
        if(row==ch.length-1 && col==ch[0].length-1)
            return true;

        if(row==ch.length || col==ch[0].length || ch[row][col]=='X' || visited[row][col]==1)
            return false;

        visited[row][col]=1;

        //Right
        ratmaze(ch,row,col+1,visited);

        //Down
        ratmaze(ch,row+1,col,visited);

        visited[row][col]=0;

        return true;
    }

    private static void print(int[][] visited,int row,int col)
    {
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                System.out.print(visited[row][col]+" ");
            }
            System.out.println();
        }
    }

}

Answer 1

您的代码有两个问题。首先来自您阅读输入字符的方式。 Scanner.next() returns 一整令牌。在这种情况下，标记是 "word" - 由空格或行的 start/end 限制的东西。在您的示例中，输入 "OXOO" 是一个标记。您需要以在外循环中读取令牌然后访问特定位置的字符的方式修改您的阅读。你可以这样做：

for (int i = 0; i < N; i++) {
    String token = sc.next();
    for (int j = 0; j < M; j++) {
        ch[i][j] = token.charAt(j);
    }
}

它 "worked" 你做的方式，但要求每个字符用空格分隔。

修复后，您将在 print() 方法中得到 ArrayIndexOutOfBoundsException。打印数组时应该使用 i 和 j，而不是 row 和 col。

这将产生一些输出。我不确定这是否是您期望的输出。

在 java 中使用回溯法解决迷宫问题

Rat in a maze problem using backtracking in java

java

recursion

backtracking