Выделение области одинаковых соседствующих элементов в матрице - 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;
    }
}

Оцени полезность:

13   голосов , оценка 3.769 из 5
Похожие ответы