Выделение подмассива

Question

Выделение подмассива

Рейтинг: 0Ответов: 1Опубликовано: 06.07.2011

Имеется массив из нулей и единиц. Нужно выделить ПОДМАТРИЦУ, в виде квадратной матрицы из единиц. Нужен именно алгоритм этого выделения.

Добавлено.

int i, j, n, m;
int a[50][50], B[50][50];
srand (GetTickCount ());

puts ("\n Input n,m:");
scanf ("%d %d", &n, &m);

printf ("\n Array a \n");

/*sozdanie mtarici iz 1 and 0*/
for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
    {
        a[i][j] = rand () % 2;
        printf ("%5.2d%c", a[i][j], (j == m - 1) ? '\n' : ' ');
    }

c# алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Задание всё же недостаточно специфицировано. Вот решение, печатающее координаты искомых матриц размером больше 2x2 (в т.ч. вложенные решения -- в матрице 3x3 будут три матрицы 2x2).

#include <iostream>
#include <windows.h>
using namespace std;
int adim (int a[50][50], int n, int m, int i, int j) {
     int t, c;
     c = 1;
     while (1) {
         // проверяем следующую границу
         if (i+c == n || j+c == m) goto ex;
         for(t = i; t <= i + c; t++)
             if(a[t][j+c] == 0) goto ex;
         for(t = j; t < j+c; t++)
             if(a[i+c][t] == 0) goto ex;
         c++;
     }
ex: return c;
}

int main() {
     int i,j,n,m,c;
     int a[50][50];
     srand(GetTickCount());
     cerr << "Input n,m:" << endl;
     cin >> n >> m;
     cout << "Array a" << endl;
     /* sozdanie mtarici iz 1 and 0*/
     for(i=0;i<n;i++) {
         for(j=0;j<m;j++) {
             cout << (a[i][j]=rand()%2);
             if (j+1 < m) cout << " ";
         }
         cout << endl;
     }
     for(i=0; i<n; i++)
         for(j=0; j<m; j++)
             if (a[i][j] && (c = adim(a, n, m, i, j)) > 1)
                 cout << i << ' ' << j << ' ' << c << endl;
     return 0;
}

Ну нетерпимый эстетами goto можно заменить исключениями.

UPD c - размер, высота/ширина. В функции adim это счётчик цикла. Проверяются ячейки (i+c,j)...(i+c,j+c) и (i,j+c)...(i+c,j+c) -- правая и нижняя кромка (с на 1 меньше размера,для матрицы 2x2 c==1). При удачной проверке c инкрементируется.

Выделение подмассива

Ответы