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 you have read our privacy policy.

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