2d массив, все значения смежны

Question

Мне нужен быстрый способ проверить, является ли массив 2d полностью смежным, то есть все значения смежны с другими одинаковыми значениями. Смежные означает четыре основных направления.

This would be an adjacent array 
[1 1 2] 
[1 2 2] 
[3 3 3] 

This isn't 
[1 2 1] 
[1 2 2] 
[3 3 3] 

This is 
[1 2 4] 
[1 2 2] 
[3 3 3] 

До сих пор, я попробовал O (M * N) метод, где я пройти через весь массив и проверить, если хотя бы один из соседей имеет то же значение. Я ищу, возможно, более быстрый способ.

EDIT: только что заметил, что мой метод даже не работает правильно. например:

This should fail (not all of the 1s are adjacent) 
[1 2 1] 
[1 2 1] 
[3 3 3] 

Так что теперь мне нужен фактический алгоритм для этого.

Answer 1

Мне напомнили об игре Сапер.

1. Внешняя петля: сканирование всего массива (по строкам слева направо). Это должно найти следующую позицию для внутреннего цикла. Если у нас не был посещен в этом положении из внутреннего контура, а номер на это положение еще не было видно, запустите внутренний контур на этом . Если мы уже видели номер в этой позиции, то матрица не является «смежной».

2. Внутренний контур: найдите все соседние ячейки с таким же номером и отметьте их как посетил (часть сапера). Запишите это число как и вернитесь во внешний цикл.

Это требует булевой матрицы, показывающий «посетили» позиции (тот же самый размер, как массив сканируемого) и логическое список чисел [1..n], которые были «посетили».

Answer 2

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

1. Найдите connected components labeling вашей матрицы
2. для каждого значения матрицы сохранить список меток компонентов он принадлежит.
3. Если какое-либо значение уже имеет связанную с ним метку, остановитесь, матрица не будет «смежной». Если нет, то матрица «смежна».

Answer 3

Я просто хочу упомянуть, что вы не можете создать алгоритм, который лучше, чем O(M*N) (конечно, это наихудшая сложность), потому что в худшем случае вам придется посетить все элементы.

Как вы сказали, что ваша O(M*N) алгоритм не работает для всех случаев, вы можете решить это с помощью BFS и Time complexity is O(M*N)

if(no.of connected components == no.of distinct elements) { 
    return true; 
}else{ 
    return false; 
} 

Как найти число связных компонент?

 yourFunction(int[][] matrix){ 
     boolean visited[][]; 
     for(int i=0;i<m;i++){ 
      for(int j=0;j<n;j++){ 
       if(!visited[i][j]){ 
        BFS(matrix,i,j); 
        connectedComponents++; 
       } 
      } 
     } 
     int distinctNumbers = findDistinctNumbers(matrix); // you can write this function easily. 
    } 
    void BFS(int[][] martix, int i,int j){ 
     queue<Point> queue = new LinkedList<>(); 
     queue.add(new Point(i,j)); 
     while(queue.isEmpty()){ 
      Point point = queue.poll(); 
       for each neighbour of point 
        if neighbour is not visited && neighbour value =current point value 
         add neighbour to queue; 
     } 
    }