时间戳

首页 > 解决方案 > 从矩阵的一点移动到零的位置

java - 从矩阵的一点移动到零的位置

问题描述

我应该用递归和迭代来编程。我的递归代码贴在底部。MagicBoard 是一款单人游戏，使用类似于国际象棋的棋盘，由 d×d 方格组成，d 介于 5 和 20 之间，每个方格包含一个介于 0 和 d -1 之间的整数。游戏规则很简单。圆圈标记板上的开始位置。圆圈中的整数 (n) 表示圆圈可以在棋盘上移动 n 个方格。在一个步骤中，圆可以向东或向西或向北或向南移动 n 个方格。在每一步，选择的方向都是固定的。圆圈不能移出棋盘。唯一合法的起始位置是四个角方块。棋盘必须恰好包含一个以零为值的目标方格，该方格可以位于棋盘上的任何位置，但其位置不能与起始位置相同。 在此处输入图像描述 例如，在上面的例子中，圆可以向东或向南移动 4 个方格。所有其他动作都是非法的。游戏的目标是将圆圈移动到包含零值的目标方格。在下面给出的配置中，您可以通过以下步骤来解决游戏： 在此处输入图像描述

下一个示例显示在某些情况下，无法从给定的起始位置到达目标方格 在此处输入图像描述

这是我的代码不起作用：


import java.util.Scanner;

public class A2Rcs {
    
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        System.out.println("\nEnter board size: ");
        int size = input.nextInt();
        
        int[][]board = new int[size][size];
        for (int i = 0; i<size; i++) {
            System.out.println("\nEnter the row: ");
            for (int j = 0; j<size; j++) {
                board[i][j] = input.nextInt();
            }
        }
        
        System.out.println("\nData you entered: ");
        for(int x = 0; x< size; x++){
            for(int y = 0 ; y< size; y++){ 
                System.out.print(board[x][y]);
            } 
            System.out.println(); 
        }
        
        System.out.println("\nEnter starting position: ");
        int p1 = input.nextInt();
        int p2 = input.nextInt();
        
        if (magicBoard(p1, p2, board, size))
            System.out.println("Solvable");     
    }
    
    public static Boolean magicBoard(int p1, int p2, int[][] board, int size) {
        boolean result = false;
        int temp;

        while(!result) {
            if(board[p1][p2] == 0) {
                System.out.println("Reached 0.");
                result = true;
                break;
            }           
            
            //can only down
            if((p1+board[p1][p2]) < size && (p1-board[p1][p2]) < 0 && ((p2+board[p1][p2]) > size && (p2-board[p1][p2]) < 0)) {
                temp = board[p1+board[p1][p2]][p2];

                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false;
                    break;
                }
                // If don't go back and forth, then we continue
                else {
                    p1 = p1+board[p1][p2];
                    System.out.print("Move south " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }
            //can only up
            else if((p1+board[p1][p2]) > size && (p1-board[p1][p2]) > 0 && ((p2+board[p1][p2]) > size && (p2-board[p1][p2]) < 0)){
                temp = board[p1-board[p1][p2]][p2];
                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false;
                    break;
                }
                else {
                    p1 = p1-board[p1][p2];
                    System.out.print("Move north " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }
            //can only up right
            else if((p2+board[p1][p2])<size && (p2-board[p1][p2])<0 && ((p1+board[p1][p2])>size && (p1-board[p1][p2])<0)) {
                temp = board[p1][p2+board[p1][p2]];
                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false;
                    break;
                }
                else {
                    p2 = p2+board[p1][p2];
                    System.out.print("Move east " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }
            //can only left
            else if((p2+board[p1][p2]) > size && (p2-board[p1][p2])> 0 && ((p1+board[p1][p2])>size && (p1-board[p1][p2])<0)) {
                temp = board[p1][p2-board[p1][p2]];
                if(board[p1][p2] == temp) {
                    System.out.print("The MagicBoard is unsolvable");
                    result = false; 
                    break;
                }
                else {
                    p2 = p2-board[p1][p2];
                    System.out.print("Move west " + board[p1][p2] + ", ");
                    magicBoard(p1, p2, board, size);
                }
            }

            // can any direction
            else {
                // try moving south
                SOUTH:
                    if(p1-board[p1][p2] < 0 && p1-board[p1][p2] > -size) {
                        temp = board[p1+board[p1][p2]][p2];
                        // Verify if we go back and forth if we go south, if we do, then we the result will be 
                        if(board[p1][p2] == temp) {
                            break SOUTH;
                        }
                        else {
                            p1 = p1+board[p1][p2];
                            System.out.print("Move south " + board[p1][p2] + ", ");
                            magicBoard(p1, p2, board, size);
                        }
                    }
                NORTH: 
                    if(p1-board[p1][p2] > 0 && p1-board[p1][p2] < size) {
                        temp = board[p1-board[p1][p2]][p2];
                        if(board[p1][p2] == temp) {
                            break NORTH;
                        }
                        else {
                            p1 = p1-board[p1][p2];
                            System.out.print("Move north " + board[p1][p2] + ", ");
                            magicBoard(p1, p2, board, size);
                        }
                    }
                    
                    // try moving east
                EAST:
                    if(p2-board[p1][p2] < 0 ) {
                        temp = board[p1][p2+board[p1][p2]];
                        // If will go back and forth at that position, then we exit the EAST label and we go to the next label
                        if(board[p1][p2] == temp) {
                            System.out.print("The MagicBoard is unsolvable");
                            break EAST;
                        }
                        else {
                            p2 = p2+board[p1][p2];
                            System.out.print("Move east " + board[p1][p2] + ", ");
                            magicBoard(p1, p2, board, size);
                        }
                    }
                    // Try moving west  
                WEST:
                    if(p2-board[p1][p2] > 0) {
                        temp = board[p1][p2-board[p1][p2]];
                        // If we go back and forth in that position, then we exit the EAST label
                        if(board[p1][p2] == temp) {
                            System.out.print("The MagicBoard is unsolvable");
                            result = false;
                            break WEST;
                        }
                    else {
                        p2 = p2-board[p1][p2];
                        System.out.print("Move west " + board[p1][p2] + ", ");
                        magicBoard(p1, p2, board, size);
                    }
                }
            }
        }

        return result;
    }
}

我已经为此工作了一个星期，但仍然无法弄清楚。我不确定在此处发布是否合适，但感谢您提供任何类型的帮助

编辑错误在这里： 在此处输入图像描述

标签： javaalgorithmrecursion

解决方案

我们可以写更少的代码，这样更容易思考和考虑它的逻辑。首先，很明显我们不需要多次访问一个单元格。我们可以使用回溯程序，标记和取消标记访问的单元格。我不精通 Java，所以我希望这段 JavaScript 代码易于翻译：

function backtrack(M, i, j, visited){
  // Reached the goal!
  if (M[i][j] == 0)
    return true;

  const d = M.length;
  const move = M[i][j];

  // Try visiting all directions
  if (i + move < d && !visited[i + move][j]){
    visited[i + move][j] = true;
    if (backtrack(M, i + move, j, visited))
      return true;
    visited[i + move][j] = false;
  }
  if (i - move >= 0 && !visited[i - move][j]){
    visited[i - move][j] = true;
    if (backtrack(M, i - move, j, visited))
      return true;
    visited[i - move][j] = false;
  }
  if (j + move < d && !visited[i][j + move]){
    visited[i][j + move] = true;
    if (backtrack(M, i, j + move, visited))
      return true;
    visited[i][j + move] = false;
  }
  if (j - move >= 0 && !visited[i][j - move]){
    visited[i][j - move] = true;
    if (backtrack(M, i, j - move, visited))
      return true;
    visited[i][j - move] = false;
  }
  return false;
}

function f(M, start_i, start_j){
  const d = M.length;
  const visited = new Array(d);
  for (let i=0; i<d; i++)
    visited[i] = new Array(d).fill(false);
  visited[start_i][start_j] = true;
  return backtrack(M, start_i, start_j, visited);
}

var board_1 = [
  [4, 2, 1, 3, 1],
  [2, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 3, 1, 2, 0]
];

var board_2 = [
  [1, 4, 1, 3, 1],
  [4, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 4, 1, 2, 0]
];

console.log(f(board_1, 0, 0));
console.log(f(board_2, 0, 0));

这是一个版本，它也为找到的第一个有效路径获取移动：

function backtrack(M, i, j, visited){
  // Reached the goal!
  if (M[i][j] == 0)
    return [[i,j]];

  const d = M.length;
  const move = M[i][j];

  // Try visiting all directions
  if (i + move < d && !visited[i + move][j]){
    visited[i + move][j] = true;
    const ms = backtrack(M, i + move, j, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i + move][j] = false;
  }
  if (i - move >= 0 && !visited[i - move][j]){
    visited[i - move][j] = true;
    const ms = backtrack(M, i - move, j, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i - move][j] = false;
  }
  if (j + move < d && !visited[i][j + move]){
    visited[i][j + move] = true;
    const ms = backtrack(M, i, j + move, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i][j + move] = false;
  }
  if (j - move >= 0 && !visited[i][j - move]){
    visited[i][j - move] = true;
    const ms = backtrack(M, i, j - move, visited)
    if (ms.length)
      return [[i,j]].concat(ms);
    visited[i][j - move] = false;
  }
  return [];
}

function f(M, start_i, start_j){
  const d = M.length;
  const visited = new Array(d);
  for (let i=0; i<d; i++)
    visited[i] = new Array(d).fill(false);
  visited[start_i][start_j] = true;
  return backtrack(M, start_i, start_j, visited);
}

var board_1 = [
  [4, 2, 1, 3, 1],
  [2, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 3, 1, 2, 0]
];

var board_2 = [
  [1, 4, 1, 3, 1],
  [4, 3, 2, 1, 4],
  [3, 2, 3, 1, 4],
  [1, 3, 4, 2, 3],
  [3, 4, 1, 2, 0]
];

console.log(JSON.stringify(f(board_1, 0, 0)));
console.log(JSON.stringify(f(board_2, 0, 0)));

推荐阅读