Поиск подматрицы в матрице

266

23 января 2019, 19:50

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

Я захотел решить задачу прямо, путём пребора каждого символа. Алгоритм такой:
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); }}}

Answer 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
          }
      }
}