2

Preciso comparar duas matrizes bidimensionais (int[][]) de tamanhos diferentes, sendo as duas formadas por valores inteiros (1 ou 0), para verificar se existe a matriz menor dentro da matriz maior.

Exemplo de matriz maior:

Matriz maior

Exemplo de matriz menor:

Não estou conseguindo criar as restrições para que percorra apenas um pedaço da maior matriz e caso um dos valores já não seja igual ela já passe a percorrer outra parte da matriz maior para ir comparando com a matriz menor e assim consequentemente até verificar se existe a matriz menor dentro da matriz maior.

6
  • 2
    O que você já tentou?
    – Jéf Bueno
    Commented 20/10/2015 às 10:08
  • Editei a pergunta, pra tentar melhorar a compreensão.
    – F L.T
    Commented 20/10/2015 às 22:12
  • A pergunta está fechada, mas votei para reabrir porque já tenho uma resposta. Commented 21/10/2015 às 6:40
  • 1
    @VictorStafusa a outra pergunta votei por reabrir pois se tratando de frameworks é mais fácil "definir", já nesta não tem bem da onde começar, mas parece que vale reabrir, já que tem a resposta. Já votei.
    – Syzoth
    Commented 21/10/2015 às 15:34
  • 1
    @FL.T se a resposta lhe respondeu a duvida, então marque-a como correta, leia: meta.pt.stackoverflow.com/q/1078/3635
    – Syzoth
    Commented 22/10/2015 às 1:03

2 Respostas 2

6

Basicamente, primeiro você identifica qual é a matriz maior e qual é a menor. Com isso, você usa 4 laços for aninhados um dentro do outro.

  • O laço externo percorre a de 0 até alturaMaior - alturaMenor (inclusive).
  • O segundo laço percorre b de 0 até larguraMaior - larguraMenor (inclusive).
  • O terceiro laço percorre c de 0 até alturaMenor (exclusive).
  • O mais interno percorre d de 0 até larguraMenor (exclusive).

A condição de parada dos dois laços interiores se dá ao fato de que eles servem para percorrer a matriz menor.

A condição de parada dos dois laços exteriores ocorre porque eles têm que percorrer apenas as posições da matriz maior que podem estar no canto superior esquerdo da matriz menor, e tais posições são obtidas subtraindo os tamanhos.

Com isso os dois laços externos vão percorrer todas as possíveis posições da matriz maior aonde poderia ocorrer a matriz menor. Os dois laços internos comparam as posições da matriz menor com a correspondente na matriz maior. Essa comparação se dá ao comparar matrizMaior[a + c][b + d] com matrizMenor[c][d]. Se forem diferentes, você continua no segundo laço, pois isso significa que a matriz menor não está nessa posição da maior. Se o terceiro laço finalizar sem ser interrompido, é porque você testou todas as posições da matriz menor a partir de uma posição da matriz maior, e todas as posições coincidiram, e portanto neste caso a matriz menor está dentro da maior e você devolve true. Se o primeiro laço finalizar sem ser interrompido, é porque você testou todas as posições da matriz maior e não encontrou a menor a partir de nenhuma delas, o que prova que a menor não existe dentro da maior e você devolve false.

No código abaixo, eu usei int[][], mas o mesmo princípio funciona para qualquer outro tipo de dado em forma de matriz (como a sua só tem zeros e uns, talvez você esteja usando boolean[][]).

import java.util.Objects;

public class ComparaMatrizes {
    public static boolean matrizContem(int[][] matrizMaior, int[][] matrizMenor) {
        Objects.requireNonNull(matrizMaior, "As matrizes não devem ser nulas.");
        Objects.requireNonNull(matrizMenor, "As matrizes não devem ser nulas.");

        // Computa o tamanho das matrizes. 
        int alturaMenor = matrizMenor.length;
        int larguraMenor = alturaMenor == 0 ? 0 : matrizMenor[0].length;
        int alturaMaior = matrizMaior.length;
        int larguraMaior = alturaMaior == 0 ? 0 : matrizMaior[0].length;

        // [Opcional] Rejeita matrizes que tiverem linhas com larguras heterogêneas.
        for (int t = 1; t < alturaMaior; t++) {
            if (matrizMaior[t].length != larguraMaior) throw new IllegalArgumentException("Ambas as matrizes devem ter larguras homogêneas.");
        }
        for (int t = 1; t < alturaMenor; t++) {
            if (matrizMenor[t].length != larguraMenor) throw new IllegalArgumentException("Ambas as matrizes devem ter larguras homogêneas.");
        }

        // Percorre as linhas da matriz maior para procurar a menor.
        for (int a = 0; a <= alturaMaior - alturaMenor; a++) {
            // Percorre as colunas da matriz maior para procurar a menor.
            r: for (int b = 0; b <= larguraMaior - larguraMenor; b++) {

                // Tendo a posição [a][b] da matriz maior como correspondente ao possível canto superior esquerdo da matriz menor,
                // verifica se essa posição contém a matriz menor ao percorrer ambas as matrizes juntas a partir desse ponto.
                // Começa percorrendo as linhas de ambas as matrizes.
                for (int c = 0; c < alturaMenor; c++) {
                    // Percorre as colunas de ambas as matrizes.
                    for (int d = 0; d < larguraMenor; d++) {

                        // Se as coordenadas tiverem valores diferentes, então essa posição da matriz maior não contém a menor.
                        // Dessa forma, se for esse o caso, interrompe o processo de percorrer ambas as matrizes juntas e avança para a
                        // próxima possibilidade na matriz maior.
                        if (matrizMaior[a + c][b + d] != matrizMenor[c][d]) continue r;
                    }
                }

                // Se terminou de percorrer ambas as matrizes (a maior a partir da posição [a][b]) e todas as posições forem iguais, então a matriz menor está dentro da maior.
                return true;
            }
        }

        // Se terminou de percorrer a matriz maior e não encontrou a menor, então é porque a menor não está dentro da maior.
        return false;
    }
}

Note também a lógica de validação das matrizes. O programa exige que ambas as matrizes sejam não-nulas e que todas as linhas de cada matriz tenham a mesma largura (ou seja, o tamanho das linhas tem que ser homogêneo).

Adaptar o algoritmo para funcionar com matrizes de tipos mais complexos (por exemplo, matrizes de Strings) é fácil, e na maioria dos casos é necessário apenas adaptar a condição do if (por exemplo, usar equals com ! ao invés de !=).

Inclusive já usei esse mesmo algoritmo para procurar uma imagem dentro de uma outra imagem. As adaptações que fiz foram bem simples, apenas trocando o acesso aos índices das matrizes por acessos a pixels e fazendo a condição do if ignorar os pixels transparentes da imagem procurada. Com mais adaptações no algoritmo, daria para fazer coisas como filtragem de cores e procura de subimagens parecidas ao invés de exatamente idênticas.

E por fim, aqui vai um código para testar o método acima. Para todos os testes ele acaba escrevendo Ok no console:

public static void main(String[] args) {
    int[][] a = {
        {1, 2, 3, 4, 5},
        {6, 7, 8, 9, 0},
        {5, 4, 3, 2, 1},
        {0, 9, 8, 7, 6}
    };
    int[][] b = {
        {7, 8},
        {4, 3}
    };
    int[][] c = {
        {2, 1},
        {7, 6}
    };
    int[][] d = {
        {4, 3}
    };
    int[][] e = {
        {9}, {2}
    };
    int[][] f = {
        {7, 9}
    };
    int[][] g = {
        {3}, {3}
    };
    int[][] h = {{1, 2, 3, 4, 5, 6}};
    int[][] i = {{1}, {2}, {3}, {4}, {5}, {6}};
    int[][] j = {{}, {}, {}, {}, {}};
    int[][] k = {};
    int[][] m = {{}, {}};

    System.out.println(matrizContem(a, a) ? "Ok 01" : "Erro 01"); // A matriz "a" contém a si mesma: true
    System.out.println(matrizContem(a, b) ? "Ok 02" : "Erro 02"); // A matriz "a" contém "b" em [1][1]: true
    System.out.println(matrizContem(a, c) ? "Ok 03" : "Erro 03"); // A matriz "a" contém "c" em [2][4]: true, este daqui testa o limite da busca na matriz maior.
    System.out.println(matrizContem(a, d) ? "Ok 04" : "Erro 04"); // A matriz "a" contém "d" em [2][1]: true
    System.out.println(matrizContem(a, e) ? "Ok 05" : "Erro 05"); // A matriz "a" contém "e" em [1][3]: true
    System.out.println(matrizContem(b, a) ? "Erro 06" : "Ok 06"); // A matriz menor não pode conter a maior: false
    System.out.println(matrizContem(a, f) ? "Erro 07" : "Ok 07"); // A matriz "a" não contém "f": false
    System.out.println(matrizContem(a, g) ? "Erro 08" : "Ok 08"); // A matriz "a" não contém "g": false
    System.out.println(matrizContem(a, h) ? "Erro 09" : "Ok 09"); // A matriz "a" não contém "h", pois "h" é mais larga que "a": false
    System.out.println(matrizContem(a, i) ? "Erro 10" : "Ok 10"); // A matriz "a" não contém "i", pois "i" é mais alta que "a": false
    System.out.println(matrizContem(a, j) ? "Erro 11" : "Ok 11"); // A matriz "a" não contém "j", pois "j" é mais alta que "a", embora tenha largura zero: false
    System.out.println(matrizContem(a, k) ? "Ok 12" : "Erro 12"); // A matriz "a" contém "k", pois "k" é vazia: true
    System.out.println(matrizContem(a, m) ? "Ok 13" : "Erro 13"); // A matriz "a" contém "m", pois "m", apesar de ter largura zero, tem altura que cabe em "a": true
    System.out.println(matrizContem(k, k) ? "Ok 14" : "Erro 14"); // A matriz vazia "k" contém a si mesma: true

    // Testa as condições de exceções:
    int[][] matrizRuim = {{1, 2, 3}, {4, 5}, {}, {6}, {7, 8, 9, 10}}; // Argh! Linhas de tamanhos diferentes!
    try {
        matrizContem(null, null);
        System.out.println("Erro 15A");
    } catch (NullPointerException esperado) {
        System.out.println("As matrizes não devem ser nulas.".equals(esperado.getMessage()) ? "Ok 15" : "Erro 15B");
    }
    try {
        matrizContem(a, null);
        System.out.println("Erro 16A");
    } catch (NullPointerException esperado) {
        System.out.println("As matrizes não devem ser nulas.".equals(esperado.getMessage()) ? "Ok 16" : "Erro 16B");
    }
    try {
        matrizContem(null, a);
        System.out.println("Erro 17A");
    } catch (NullPointerException esperado) {
        System.out.println("As matrizes não devem ser nulas.".equals(esperado.getMessage()) ? "Ok 17" : "Erro 17B");
    }
    try {
        matrizContem(matrizRuim, matrizRuim);
        System.out.println("Erro 18A");
    } catch (IllegalArgumentException esperado) {
        System.out.println("Ambas as matrizes devem ter larguras homogêneas.".equals(esperado.getMessage()) ? "Ok 18" : "Erro 18B");
    }
    try {
        matrizContem(a, matrizRuim);
        System.out.println("Erro 19A");
    } catch (IllegalArgumentException esperado) {
        System.out.println("Ambas as matrizes devem ter larguras homogêneas.".equals(esperado.getMessage()) ? "Ok 19" : "Erro 19B");
    }
    try {
        matrizContem(matrizRuim, b);
        System.out.println("Erro 20A");
    } catch (IllegalArgumentException esperado) {
        System.out.println("Ambas as matrizes devem ter larguras homogêneas.".equals(esperado.getMessage()) ? "Ok 20" : "Erro 20B");
    }
}
2
  • 2
    Bem interessante, gostei da abordagem que usou ;) Commented 21/10/2015 às 17:14
  • De mão beijada a resposta kk, parabéns, ainda não consegui testar, mas inicialmente parece ser interessante, basta o AP da pergunta se seguir pelo 20A por exemplo (quase uma depuração) que ele vai entender a lógica no uso. Obrigado pela contribuição e esforço.
    – Syzoth
    Commented 21/10/2015 às 19:26
0
    public static void compareArrays(int[] array1, int[] array2) {
        boolean b = true;
        if (array1 != null && array2 != null){
          if (array1.length != array2.length)
              b = false;
          else
              for (int i = 0; i < array2.length; i++) {
                  if (array2[i] != array1[i]) {
                      b = false;    
                  }                 
            }
        }else{
          b = false;
        }
        System.out.println(b);
    }
1
  • Resposta incorreta. Isso daí compara se dois arrays têm conteúdos idênticos, o que tem pouca ou nenhuma relação com o problema da pergunta, que é procurar uma matriz dentro de outra matriz. Commented 21/10/2015 às 6:09

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .