Размеры "областей" из одинаковых элементов в матрице

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

Находясь в некоторой стартовой точке, я хочу узнать "размер области" (количество элементов), заполненной тем же значением, например, для тройки в левом верхнему углу это значение равно 5, а для нуля в правом нижнем 41.

Мы закрасили участки матрицы разными цветами ещё и потому, что алгоритм можно применять для подсчёта площадей, занятых на изображении каким-либо цветом, или поиска допустимой области, в которой может перемещаться игровой персонаж и т.п. задач.

Примем, что стартовая точка, с которой начинается определение размера области, в программе задана парой координат строки и столбца матрицы seed_row и seed_col.

Если мы позволяем себе "портить" данные матрицы (например, закрашивать контур), решение сводится к тривиальной рекурсии, реализуемой функцией s:

#include <stdio.h>

const int n =10;
int data[n][n] = {
 {3,3,3,3,1,1,4,4,4,4},
 {3,1,1,1,1,1,4,4,0,4},
 {2,2,1,1,1,1,4,4,4,4},
 {0,2,1,1,1,1,4,4,0,0},
 {0,2,2,2,2,2,2,4,4,4},
 {0,0,0,0,0,2,2,2,4,4},
 {0,0,0,0,0,0,2,2,4,0},
 {0,0,0,0,0,0,4,4,4,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0}
};

int s (int seed,int r,int c) {
 if (r<0 || r>n-1 || c<0 || c>n-1 || data[r][c]<0) return 0;
 else if (data[r][c]==seed) {
  data[r][c]=-data[r][c];
  return (1 +
  (r>0 ? s(seed,r-1,c) : 0) +
  (r<n-1 ? s(seed,r+1,c) : 0) +
  (c>0 ? s(seed,r,c-1) : 0) +
  (c<n-1 ? s(seed,r,c+1) : 0));
 }
 else return 0;
}

int main(){
 int seed_row = 3, seed_col = 1;
 printf ("\nSeed data = %d",data[seed_row][seed_col]);
 printf ("\nN=%d",s(data[seed_row][seed_col],seed_row,seed_col));
 fflush (stdin);
 getchar ();
 return 0;
}

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

Если мы не хотим менять элементы матрицы, нам придётся где-то хранить список координат уже пройденных элементов, иначе рекурсия всё равно зациклится, сколько бы ухищрений мы ни придумывали, чтоб этого избежать. Например, из элемента 1,1 мы можем перейти к элементу 0,1, а затем, так как из каждого элемента перебираются все возможные пути, снова вернуться к 1,1 и т.д. Введение дополнительных переменных, например, запоминающих направление, откуда мы пришли к данному элементу, ничего не даст - просто циклы в рекурсии станут более длинными и трудноуловимыми.

За добавление элемента в путь будет отвечать метод push_in_way, а за проверку того, есть ли узел в ранее обработанной части матрицы - метод in_way. Сам "путь" - это обычный динамический массив way со счётчиком элементов way_cnt. В массиве way чередуются номера обработанных строк и столбцов матрицы данных. Так как мы выходим на один элемент "за границы" матрицы, контролируя элементы крайних столбцов и строк, размерность вектора "пути" будет разумно установить в значение (n*n+4*n+4)*2 - записанное в скобках число элементов матрицы размерностью (n+2)*(n+2) умножается на 2, так как сохраняются номер строки и номер столбца каждого элемента, где мы побывали, а в "худшем" случае исходная матрица n*n состоит из всех одинаковых элементов.

Нули в данных теперь коду не страшны, и матрицу он не меняет.

#include <stdio.h>

const int n =10;
int data[n][n] = {
 {3,3,3,3,1,1,4,4,4,4},
 {3,1,1,1,1,1,4,4,0,4},
 {2,2,1,1,1,1,4,4,4,4},
 {0,2,1,1,1,1,4,4,0,0},
 {0,2,2,2,2,2,2,4,4,4},
 {0,0,0,0,0,2,2,2,4,4},
 {0,0,0,0,0,0,2,2,4,0},
 {0,0,0,0,0,0,4,4,4,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0}
};

int dirs[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

int *way=NULL;
int way_cnt = 0;

int in_way (int r,int c) {
 for (int i=0; i<way_cnt; i+=2) if (way[i]==r && way[i+1]==c) return 1;
 return 0;
}

void push_in_way (int r,int c) { way[way_cnt++] = r; way[way_cnt++] = c; }

int s (int seed,int r,int c) {
 if (r<0 || r>n-1 || c<0 || c>n-1 || data[r][c]!=seed) return 0;
 else {
  int cnt = 1;
  for (int dir=0; dir<4; dir++)
  if (!in_way(r+dirs[dir][0],c+dirs[dir][1])) {
   push_in_way (r+dirs[dir][0],c+dirs[dir][1]);
   cnt+=s(seed,r+dirs[dir][0],c+dirs[dir][1]);
  }
  return cnt;
 }
}

int main(){
 int seed_row = 3, seed_col = 1;

 way = new int [(n*n+4*n+4)*2];
 if (way == NULL) return -1;
 for (int i=0; i<n*n*2; i++) way[i]=-1;
 way_cnt = 0;

 printf ("\nSeed data = %d",data[seed_row][seed_col]);

 push_in_way (seed_row,seed_col);
 printf ("\nN=%d",s(data[seed_row][seed_col],seed_row,seed_col));
 fflush (stdin);
 getchar ();
 return 0;
}

Обратите внимание, что перед вызовом функции s мы "положили" в путь исходную точку функцией push_in_way.

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

30.11.2014, 19:45 [11147 просмотров]