0

Есть задача поиска в матрице нужную подматрицу, пример на фото пример

Я захотел решить задачу прямо, путём пребора каждого символа. Алгоритм такой:
1)Поиск первого символа из матрицы А (например в матрице В нашли 1)
2)Проверка соседнего символа в матрице В (например рядом с 1, стоит ещё 1)
3)Проверка соседнего символ от соседа
.... и так далее, пока не найдена нужная строка в строке
4)Если мы нашли нужную строку, то проверить строку ниже (i+1)

Я не мастер высказывать свои мысли, поэтому заранее извиняюсь за текст. Кто может помочь решить данную задачу? Не обязательно писать код, можно предложить другой алгоритм или поправить мой.

Написал код, правда он работает не так как надо (хотя иногда выдаёт нужный результат)

 int[][] matrixB = {
                    {1,2,3,4,5,6,7,8,9,0},
                    {0,1,1,2,1,2,1,2,3,1},
                    {2,1,2,3,1,1,2,1,1,0},
                    {6,7,7,8,1,2,3,4,6,8}
};

int[][] matrixA = {
 {1,1,2,1},
     {1,2,3,4}};
 for (int i = 0; i < matrixB.length - 1 ; i++){
     for (int j = 0; j < matrixB[i].length - 1; j++) {
            for (int k = 0; k <  matrixA.length - 1; k++) {
                for (int l = 0; l < matrixA[k].length - 1; l++) {

                         if((matrixA[k][l] == matrixB[i][j]) && (matrixA[k+1][l] == matrixB[i+1][j]) && (matrixA[k+1][l+1] == matrixB[i+1][j+1]))
                             System.out.println(i +""+ j); }}}

1 ответ 1

1

Пошаговое сравнение можно сделать примерно так (ideone):

для каждой потенциальной позиции левого угла малой матрицы в большой проверяете, что все элементы совпадают:

for (int i = 0; i <= matrixB.length - matrixA.length ; i++){
   for (int j = 0; j <= matrixB[0].length - matrixA[0].length; j++) {
         boolean success = true;

         for (int k = 0; k <  matrixA.length - 1; k++) {
             for (int l = 0; l < matrixA[0].length - 1; l++) {
                 if (matrixB[i + k][j + l] != matrixA[k][l]) {   
                     success = false;
                     break;
                 }  
              }
              if (!success) break;
          }
          if (success) {
               // код в случае совпадения матрицы. Например, здесь можно запомнить позиции i,j
          }
      }
}
5
  • Я вроде бы понял что надо делать, спасибо. Вопрос по вашему коду: Он же не отработает для поиска всей матрицы? Мне кажется что поиск идёт только для "угла". И как понять эту арифметику " matrixB.length - 1 - matrixA.length" ?
    – Temp13
    30 сен 2018 в 17:10
  • Большая матрица размером 10, малая 3. Малая может начинаться от позиции 0 до 6, дальше она просто не поместится
    – MBo
    30 сен 2018 в 17:13
  • Код "отработает для поиска всей матрицы", если она есть, т.е. все элементы совпадают, иначе - при несовпадении - произойдёт ранний выход, чтобы перейти на следующую позицию угла, т.к. в этой ловить уже нечего.
    – MBo
    30 сен 2018 в 17:28
  • Спасибо, мне всё понятно, но у меня код не работает:) Скорее всего где-то неправильно что-то делаю. Главное принцип разобрал. Успехов вам!
    – Temp13
    30 сен 2018 в 17:52
  • Увидел и исправил ошибку в двух первых циклах, не зря Вы сомневались ;) Проверил, код теперь рабочий.
    – MBo
    30 сен 2018 в 18:13

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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