0

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

Добавлено.

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' : ' ');
    }
3
  • Это что, найти максимальную цепочку единиц длиной k^2? Или исходный массив -- матрица (тогда единицы в векторном представлении будут идти с промежутками)
    – alexlz
    6 июл 2011 в 10:40
  • массив двумерный. поэтому цепочка как вариант не пойдет. исходный массив конечно матрица. и между единицами не должно быть промежутков.ведь в подматрицы (по определению промежутков нет) 0 1 1 0 1 0 1 1 0 1 пускай есть такая матрица значит квадратная подматрица 0 0 0 0 0 будет 1 1 1 1
    – Sheldon20
    6 июл 2011 в 10:49
  • Картину не грузит.
    – Sheldon20
    6 июл 2011 в 10:58

1 ответ 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 инкрементируется.

4
  • спасибо большое.я так понял после матрицы основной выводит матрицу в 3 столба. первый это i второй j а третий c (судя по алгоритму) это координаты верхнего левого угла матрицы квадратной. но что такое С в данном случае?
    – Sheldon20
    6 июл 2011 в 13:51
  • понял. еще раз спасибо
    – Sheldon20
    6 июл 2011 в 15:39
  • "эстеты" будут использовать вместо goto -> return c;
    – IAZ
    7 июл 2011 в 13:31
  • Нет, return c; -- не для "эстетов". Но мне поделом :)
    – alexlz
    7 июл 2011 в 13:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.