2D数组遍历以获得不同的7位数组合

Question

我从一本面试准备书中遇到了一个棘手的问题。你有一个3乘3的矩阵，包含整数1到9，如下所示

 1 2 3
 4 5 6
 7 8 9

如何获得唯一的7位数字组合，第一个数字全部以4开始（矩阵[1] [0]）。遍历意味着像棋盘上的车一样。水平或垂直方向的一种方式......（4125874是有效的7位数组合顺便说一句）。

我尝试编写一些代码并使用布尔访问标志进行常规2D矩阵遍历，以获得答案并将每个组合存储在hashSet中以确保唯一性但我被卡住了。任何类型的评论，提示和代码修订，让我的代码工作将不胜感激。

class Ideone
{

    void dfs(int[][] matrix, boolean visited) //considered dfs with a boolean visited flag but I am stuck. I want to make my solution recursive
    {
        boolean visited =  false;

    }

    public static HashSet<String> get7DigitCombo(int[][] matrix)
    {
        String result = "";
        int[][] cache =  matrix.clone();
        Set<String> comboSet =  new HashSet<String>();
        boolean visited =  false;

        int resultStart = matrix[1][0];

        for(int row = 1; row < matrix.length; row++)
        {
            for(int col = 0; col < matrix[0].length; col++)
            {
                if (visited == false & result.length < 7)
                {
                    result += "" + (matrix[row + 1][col] || matrix[row -1][col] || matrix[row][col+1] || matrix[row][col-1]);
                }

            }
        }

        comboSet.add(result);
        return comboSet;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        int[][] matrix =  {{1, 2, 3},
                          {4, 5, 6}, 
                          {7, 8, 9},
                          };

        HashSet<String> comboSet =  get7DigitCombo(matrix);

        System.out.print(comboSet);
    }
}

Answer 1

以下mcve演示了递归获取邻居并累积到唯一组合。 代码记录了注释：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Ideone
{
    private static final int SIZE = 7;     //size of combo 

    private static int[][] directions = {  //represents moving directions 
            {-1, 0},  //up
            { 0,-1},  //left
            { 0, 1},  //right
            { 1, 0}   //down
    };

    public static void main (String[] args) throws java.lang.Exception
    {
        int[][] matrix =  {{1, 2, 3},
                {4, 5, 6},
                {7, 8, 9},
        };
        Set<String> comboSet =  get7DigitCombo(matrix);
        System.out.print(comboSet.size());
    }

    public static Set<String> get7DigitCombo(int[][] matrix)
    {
        Set<String> comboSet =  new HashSet<>();

        get7DigitCombo(1, 0, matrix, String.valueOf(matrix[1][0]), comboSet);
        return comboSet;
    }

     //recursively get all neighbors. generate combos by appending each neighbor 
    //combo represents a single combination. combos accumulates combination 
    static void get7DigitCombo(int row, int col, int[][] matrix, String combo, Set<String> combos){

        if(combo !=null && combo.length() == SIZE) { //when combo reached the right size, add it  
            //System.out.println(combo);
            combos.add(combo);
            return;
        }

        //get and iterate over all adjacent neighbors 
        for(int[] neighbor : getNeighbors(row, col, matrix)){
            get7DigitCombo(neighbor[0], neighbor[1], matrix, combo+neighbor[2], combos);
        }
    }

    //return list of adjacent neighbors. each neighbor is represented by
    //int[3]: row, column, value
    private static List<int[]> getNeighbors(int row, int col, int[][] matrix) {

        List<int[]> neighbors = new ArrayList<>();
        for(int[] dir : directions){
            int newRow = row + dir[0] ; int newCol = col + dir[1];
            if(isValidAddress(newRow, newCol, matrix)) {
                neighbors.add( new int[]{newRow,newCol, matrix[newRow][newCol]});
            }
        }
        return neighbors;
    }

    private static boolean isValidAddress(int row, int col, int[][] matrix) {

        if(row < 0 || col < 0) return false;
        if(row >= matrix.length || col >= matrix[row].length) return false;
        return true;
    }
} 

Answer 2

这是一个pacman问题。您必须查找或定义每个矩阵值的邻居。然后穿过矩阵，停止每个矩阵值的邻居。它通常用递归函数解析。我认为你的代码必须使用不同的方法从地面改变。