更改与一维一起使用的二维迷宫求解器 [英] changing 2-d maze solver to be used with 1-d

问题描述

给出包含构建迷宫的所有内容的代码，我要编写makeMove方法来解决迷宫，该方法已经完成并且可以正常工作.但是，一切都已完成，以便将2D数组与迷宫一起使用，并且访问，我需要对其进行编辑以与1d数组一起用于迷宫和访问.

public abstract class AbstractMaze {

protected int startRow;   // starting row
protected int startCol;   // starting column
protected int endRow;     // ending row
protected int endCol;     // ending column

/**
 * Declare the maze, 1's are walls and 0's are open
 */
protected int[][] maze;

protected AbstractMaze(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
    super();
    this.maze = maze;
    this.startRow = startRow;
    this.startCol = startCol;
    this.endRow = endRow;
    this.endCol = endCol;
}
public void solve() {
    makeMove( startRow, startCol )
}
protected abstract void makeMove( int row, int col );
}

---

public class Maze2 extends AbstractMaze
 {
public Maze2(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
    super(maze, startRow, startCol, endRow, endCol);
}
int MAX_ROWS = endRow + 1;
int MAX_COLS = endCol + 1;
boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
protected void makeMove( int row, int col )
{
    boolean found = false;
    if (row < 0 || row >= MAX_ROWS  || col < 0 || col >= MAX_COLS  || visited[row][col] || maze[row][col] == 1)
        return;

    visited[row][col] = true;
    found = row == endRow && col == endCol;

    if (!found) {
        makeMove(row, col - 1);
        makeMove(row, col + 1);
        makeMove(row - 1, col);
        makeMove(row + 1, col);
    }

我需要更改迷宫[] []到过和参观过[[] []的每个地方吗?最简单的方法是什么?

感谢所有帮助！

我假设您要将给定的2D maze数组更改为1D maze类成员.将maze成员声明为

int ROWS = maze.length;
int COLS = maze[0].length;
this.maze = new int[ROWS * COLS];

您可以将此数组索引为maze[COLS * row + col].然后，您需要将元素复制到以下位置:

for (int r = 0; r < ROWS; r++)
    for (int c = 0; c < COLS; c++)
        this.maze[COLS * r + c] = maze[r][c];

如您所见，访问元素是通过this.maze[COLS * r + c]而不是this.maze[r][c]完成的.您可以将其视为采用2D数组并将行连接在一起以形成一个长的1D数组.

同样，可以将visited数组声明为visited[MAX_COLS * MAX_ROWS]并通过visited[MAX_COLS * row + col]进行索引.

Given code that included everything to build a maze, I was to write the makeMove method to solve the maze, which I have completed and is working fine. However everything is done to use 2-D array with the maze and visited, I need to edit this to be used with 1-d array for maze and visited.

public abstract class AbstractMaze {

protected int startRow;   // starting row
protected int startCol;   // starting column
protected int endRow;     // ending row
protected int endCol;     // ending column

/**
 * Declare the maze, 1's are walls and 0's are open
 */
protected int[][] maze;

protected AbstractMaze(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
    super();
    this.maze = maze;
    this.startRow = startRow;
    this.startCol = startCol;
    this.endRow = endRow;
    this.endCol = endCol;
}
public void solve() {
    makeMove( startRow, startCol )
}
protected abstract void makeMove( int row, int col );
}

---

public class Maze2 extends AbstractMaze
 {
public Maze2(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
    super(maze, startRow, startCol, endRow, endCol);
}
int MAX_ROWS = endRow + 1;
int MAX_COLS = endCol + 1;
boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
protected void makeMove( int row, int col )
{
    boolean found = false;
    if (row < 0 || row >= MAX_ROWS  || col < 0 || col >= MAX_COLS  || visited[row][col] || maze[row][col] == 1)
        return;

    visited[row][col] = true;
    found = row == endRow && col == endCol;

    if (!found) {
        makeMove(row, col - 1);
        makeMove(row, col + 1);
        makeMove(row - 1, col);
        makeMove(row + 1, col);
    }

Do I need to change every place where maze[][] is and visited[][]? What is the simplest way to go about this?

Thanks for any and all help!

解决方案

I assume that you want to change the given 2D maze array into a 1D maze class member. Declare the maze member as

int ROWS = maze.length;
int COLS = maze[0].length;
this.maze = new int[ROWS * COLS];

You can index this array as maze[COLS * row + col]. You'll then need to copy the elements over:

for (int r = 0; r < ROWS; r++)
    for (int c = 0; c < COLS; c++)
        this.maze[COLS * r + c] = maze[r][c];

As you can see, accessing an element is accomplished via this.maze[COLS * r + c] instead of this.maze[r][c]. You can think of it as taking the 2D array and joining the rows together to form a long 1D array.

Similarly, the visited array can be declared as visited[MAX_COLS * MAX_ROWS] and indexed via visited[MAX_COLS * row + col].

这篇关于更改与一维一起使用的二维迷宫求解器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！