0

Друзья, подскажите, пожалуйста. Есть квадратная матрица NxN. Вся матрица заполнена значениями от 1 до N в произвольном порядке, разумеется с повторениями (дважды, трижды, или более раз может встретиться любое из значений от 1 до N). Требуется взять по одному значению из каждой строки матрицы так, что бы можно было составить непрерывный ряд значений от 1 до N.

Примеры входных данных:

2 2 2 3
4 3 3 4
1 1 2 2
2 1 2 2

и

1 1 1 1 1
2 2 3 4 5
5 5 5 4 5
1 1 1 5 5
1 1 1 1 5

Я привел матрицу

2 2 2 3
4 3 3 4
1 1 2 2
2 1 2 2

к виду виду

0 1 1 0
0 0 1 1
1 1 0 0
1 1 0 0

где столбец это цифра присутствующая в строке. т.е. 2 2 2 3 это 0 1 1 0 соответственно, если отсортировать строки так, чтобы значения по диагонали были равны 1, то это и есть непрерывный ряд, т.о. если отсортировать строки

1 1 0 0
1 1 0 0
0 1 1 0
0 0 1 1

то видим, что в каждой строке есть цифра, для нашего непрерывного ряда. если перевести в исходную матрицу, то получим

1 1 2 2 - 1
2 1 2 2 - 2
2 2 2 3 - 3
4 3 3 4 - 4

ну и ответ да, составить ряд можно.

берем первую строку с не нулевым элементов, и исключаем из массива первую строку и первый столбец. Получим:

1 0 0
1 1 0
0 1 1

и так далее, когда размерность массива станет 1, проверяем, если [0][0]ый элемент равен 0, пр:

0 1
0 1

, то считаем, что матрица не сходится. Если 1, то сходится.

Я перевел это в код:

     private void recur(ArrayList<ArrayList<Integer>> booleanRecursMatrix) {

for (int column = 0; column < booleanRecursMatrix.size(); column++) {
            for (int row = 0; row < booleanRecursMatrix.size(); row++) {
                if (booleanRecursMatrix.get(row).get(column) == 1) {
                    ArrayList<ArrayList<Integer>> downArray = new ArrayList<>();
                    downArray.addAll(booleanRecursMatrix);

                    System.out.println("\n" + downArray);
                    downArray.remove(row);

                    for (int irow = 0; irow < downArray.size(); irow++) {
                        downArray.get(irow).remove(column);
                    }
                    System.out.println(downArray);

                    if (downArray.size() == 1 && downArray.get(0).get(0) == 1) {
                        System.out.println("Матрица сходится, кол-во иттераций = " + this.count);
                        //break label1;
                    } else if(downArray.size() == 1 && downArray.get(0).get(0) == 0) {
                        System.out.println("Матрица не сходится");
                        break;
                    } else {
                        System.out.println("");
                        this.count += 1;
                        recur(downArray);
                    }

                }

            }
        }

Не могу понять, почему цикл не перебирает все варианты, а прекращается на первом.

1 ответ 1

1

Может кому пригодиться, решил через рекурсию. Проблема была в том, что элементы удалял в исходном массиве,а обратно не возвращал.

import java.util.ArrayList;

public class Recurs {

    boolean Flag = false;
    int count = 0;

    public void getRecurs(ArrayList<ArrayList<Integer>> matrixAr) {
        int numRow = -1;
        int index;
        for (int i = 0; i < matrixAr.size(); i++) {
            if (matrixAr.get(i).get(0)!= 1){
                break;
            }
        }
        //Получаем номера строк, которые нас удовлетворяют
        ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
        for (int row = 0; row < matrixAr.size(); row++) {
            for (int colum = 0; colum < matrixAr.size(); colum++) {
                if (matrixAr.get(row).get(0) == 1) {
                    //System.out.print(matrixAr.get(row).get(colum));
                    numRow = row;
                }
            }

            if (numRow != -1) {
                //System.out.println();
                //System.out.println("Номера строк: " + numRow);
                temp.add(matrixAr.get(numRow));
            }
            //System.out.println();
        }
        //System.out.println(matrixAr);
        //System.out.println("Получили значения, которые нас удовлетворяют: " + temp);

        //Удаляем строки из массива, потом возвращаем их обратно.
        ArrayList<Integer> delCol = new ArrayList<>();
        for (int i = 0; i < temp.size(); i++) {
            //matrixAr.remove(temp.get(i));
            matrixAr.remove(temp.get(i));
            for (int row = 0; row < matrixAr.size(); row++) {
                delCol.add(matrixAr.get(row).get(0));
                matrixAr.get(row).remove(0);
            }
            //System.out.println("Удаляем, получим: " + matrixAr);
            if (matrixAr.size() == 1 && matrixAr.get(0).get(0) == 1) {
                this.count++;
                this.Flag = true;
                //System.out.println("Ряд сходится");
            }
            getRecurs(matrixAr);
            for (int row = 0; row < matrixAr.size(); row++) {
                delCol.add(matrixAr.get(row).get(0));
                matrixAr.get(row).add(0, delCol.get(row));
            }
            matrixAr.add(temp.get(i));
            //System.out.println("Добавляем обратно, получим: " + matrixAr);
        }
    }

    public void getStat() {
        if (Flag) {
            System.out.println("Найденныйх решений: " + count);
        } else {
            System.out.println("Решений найдено небыло");
        }
    }
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.