Обход двумерного массива для получения различных комбинаций из 7 цифр

Question

Я столкнулся с непростым вопросом из книги подготовки к собеседованию, которая выходит .. У вас есть матрица 3 на 3, содержащая целые числа от 1 до 9, как показано ниже

 1 2 3
 4 5 6
 7 8 9

Как получить уникальный 7-значный номеркомбинируется с первыми числами, начиная с 4 (матрица [1] [0]).Обход должен быть похож на ход ладьи на шахматной доске ... 1 путь по горизонтали или по вертикали ... (Кстати, наличие 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

Это проблема Пакмана.Вы должны искать или определять соседей каждого значения матрицы.Затем пересечь матрицу, следуя за соседями каждого значения матрицы.Обычно разрешается с помощью рекурсивных функций.Я думаю, что ваш код должен быть изменен с нуля, используя другой подход.