Поиск в матрице подматриц из совпадающих элементов

В двумерном целочисленном массиве размерностью n*m элементы принимают только натуральные значения. Прямоугольником в матрице считается группа соседних элементов с одинаковым значением, которые вместе образуют подматрицу размером k*l, k>1, l>1. Прямоугольником нельзя считать группу элементов, принадлежащую другому прямоугольнику. Вывести координаты всех прямоугольников в заданной матрице.

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

#include <iostream>
using namespace std;

const int n=7,m=6;
int a[n][m]={
 {1,1,1,2,2,1},
 {1,1,1,2,2,2},
 {1,1,2,2,3,7},
 {4,3,3,3,3,7},
 {5,3,3,3,3,7},
 {5,6,6,7,7,7},
 {7,6,6,7,7,7}
};

int main (void) {
 int i,j,i1,j1,start_item,end_n,end_m,count,found,by_row,bad_steps;
 for (i=0; i<n-1; i++) {
  for (j=0; j<m-1; j++) {
   if (a[i][j]==0) continue;
   start_item=a[i][j];
   end_n=i+1;
   end_m=j+1;
   found=0;
   by_row=0;
   bad_steps=0;
   while (end_n<n && end_m<m) {
    count=0;
    for (i1=i; i1<=end_n; i1++) {
     for (j1=j; j1<=end_m; j1++) {
      if (a[i1][j1]==start_item) count++;
     }
    }
    if (count==(end_n-i+1)*(end_m-j+1)) {
     found=1;
     if (end_n<n-1) {
      if (bad_steps<1) { end_n++; by_row=1; continue; }
     }
     else { bad_steps=1; }
     if (end_m<m-1) {
      if (bad_steps<2) { end_m++; by_row=2; continue; }
     }
     else { bad_steps=2; }
    }
    else {
     if (found==0 && by_row==0) break;
     else if (by_row==1) { end_n--; bad_steps++; }
     else if (by_row==2) { end_m--; bad_steps++; }
    }
    if (bad_steps==2) break;
   }
   if (found) {
    cout << "(" << i << "," << j << ") - (" << end_n << "," << end_m << ")" << endl;
    for (i1=i; i1<=end_n; i1++)
    for (j1=j; j1<=end_m; j1++) a[i1][j1]=0;
   }
  }
 }
 cin.sync(); cin.get(); return 0;
}

выдача программы

Так как, по условию, элементы матрицы - натуральные числа, уже вошедшие в прямоугольники элементы будем заменять нулями. Код "портит" исходную матрицу из-за этих замен.

Также, при "неоднозначности" вида

1 1 1
1 1 1
1 1 2

выбор прямоугольника (0,0) - (2,1) или (0,0) - (1,2) зависит от порядка изменения переменных end_n и end_m, в нашем случае будет выбран первый вариант.

12.07.2014, 01:23 [12825 просмотров]