Выделение области одинаковых соседствующих элементов в матрице - C (СИ)
Формулировка задачи:
Добрый день.
Помогите решить вот эту задачку. Идея есть, но воплотить никак не могу. Идея заключается в том что бы найти в матрице елемент который равен 1, после этого проверить соседние елементы слева, справа, сверху и снизу, после чего если хоть один равен 1(например слева) двигаться дальше пока он не будет равен 0 и так далее пока не проверим остальные стороны после чего выделяем это как область(заменяя эти 1чки на другую цифру, 2 например)) и так далее. Вот как то так
Заранее спасибо.
Задана прямоугольная таблица размером n * m ( 1≤n , m≤100 ) , элементами которой являются числа 0 и 1. Будем считать , что элементы со значениями 1 образуют сплошную область с соседними по горизонтали или вертикали элементами со значениями 1. Вычислить количество таких областей и площадь самой большой из них .
Решение задачи: «Выделение области одинаковых соседствующих элементов в матрице»
textual
Листинг программы
#include <stdio.h>
#include <malloc.h>
#define MAX_SZ 32
#define N 7
#define M 8
typedef struct {
short row, col;
} pos;
typedef struct _page {
struct _page* next;
pos arr[MAX_SZ];
int cnt;
} page;
typedef struct {
page* lst;
} stack_t;
void stack_init(stack_t* st){ st->lst = NULL; }
int stack_empty(stack_t* st) { return (st->lst == NULL); }
int stack_push(stack_t* st, short row, short col);
void stack_pop(stack_t* st);
void stack_clear(stack_t* st);
void stack_top(stack_t* st, short* prow, short* pcol);
const short g_dirs[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int main(void){
stack_t st;
short row, col, r1, c1, i, j, d, s, k, m;
short mat[N][M] = {
{1,1,0,0,1,1,1,1},
{1,1,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0},
{0,0,0,0,1,1,1,0},
{1,1,0,1,1,1,1,1},
{1,1,0,0,0,0,0,0},
{1,1,1,0,0,0,1,1},
};
m = s = 0;
for(i = 0; i < N; ++i){
for(j = 0; j < M; ++j){
if(mat[i][j] != 1)
continue;
mat[i][j] += 1;
k = 0;
stack_init(&st);
stack_push(&st, i, j);
while(! stack_empty(&st)){
stack_top(&st, &row, &col);
stack_pop(&st);
++k;
for(d = 0; d < 4; ++d){
r1 = row + g_dirs[d][0];
c1 = col + g_dirs[d][1];
if((r1 < 0) || (c1 < 0) || (r1 >= N) || (c1 >= M) || (mat[r1][c1] != 1))
continue;
stack_push(&st, r1, c1);
mat[r1][c1] += 1;
}
}
++m;
if(k > s)
s = k;
}
}
printf("count area: %d\n", m);
printf("maximum S: %d\n", s);
//вывести результирующею матрицу
for(i = 0; i < N; ++i){
for(j = 0; j < M; ++j)
printf("%d ", mat[i][j]);
putchar('\n');
}
return 0;
}
//вставка
int stack_push(stack_t* st, short row, short col){
page* p = st->lst;
if(p != NULL){
if((p->cnt + 1) < MAX_SZ){
p->arr[p->cnt].row = row;
p->arr[p->cnt].col = col;
++(p->cnt);
return 1;
}
}
p = (page*)malloc(sizeof(page));
if(p == NULL)
return 0;
p->arr[0].row = row;
p->arr[0].col = col;
p->cnt = 1;
p->next = st->lst;
st->lst = p;
return 1;
}
//удаление
void stack_pop(stack_t* st){
page* p = st->lst;
if(p != NULL){
if(p->cnt > 0)
--(p->cnt);
if(p->cnt == 0){
st->lst = st->lst->next;
free(p);
}
}
}
//удаление всех
void stack_clear(stack_t* st){
while(! stack_empty(st))
stack_pop(st);
}
//получение текущих данных
void stack_top(stack_t* st, short* prow, short* pcol){
page* p = st->lst;
if((p != NULL) && (p->cnt > 0)){
*prow = p->arr[p->cnt - 1].row;
*pcol = p->arr[p->cnt - 1].col;
}
}