Форум программистов, компьютерный форум CyberForum.ru

Найти квадратную матрицу из нулей - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
OlegRuno
2 / 2 / 0
Регистрация: 28.05.2012
Сообщений: 38
15.09.2012, 15:50     Найти квадратную матрицу из нулей #1
На чёрно-белом изображении размером A строк x B столбцов необходимо найти полностью белый квадрат с максимальной площадью.
В первой строке входного файла input.txt записаны два целых числа - количество строк A и столбцов B в изображении. В следующих A строках записаны значения цвета в количестве B без пробелов: 0 - чётный, 1 - белый. Все получаемые значения целые и по модулю не превосходят 2147483647. Размер изображения не превышает 1000 x 1000. Каждая строка заканчивается переходом на новую строку.

Выходной файл output.txt состоит из одний строки. В первой строке необходимо вывести найденное значение максимальной площади без пробелов.

записывать и считывать из файла не нужно, главное алгоритм. ПОМОГИТЕ)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.09.2012, 15:50     Найти квадратную матрицу из нулей
Посмотрите здесь:

C++ Задача на квадратную матрицу
C++ Создать квадратную матрицу
Сформировать квадратную матрицу C++
найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
Сформировать квадратную матрицу; транспонировать матрицу и инвертировать порядок элементов каждой ее строки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 8
Регистрация: 24.07.2012
Сообщений: 916
15.09.2012, 16:21     Найти квадратную матрицу из нулей #2
Тебе нужен алгоритм поиска связнных областей? Есть два варианта один по проще , но требует память, другой по сложнее но не требует ее, тебе какой?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.09.2012, 16:59     Найти квадратную матрицу из нулей #3
Цитата Сообщение от OlegRuno Посмотреть сообщение
главное алгоритм. ПОМОГИТЕ)
Описание алгоритма (по моему быстрее не придумаешь):
создаем первый массив a[A+1][B+1], в котором нулевая строка и столбец заполнены нулями, а все остальное значениями из "чёрно-белого изображения размером A строк x B столбцов".
создаем второй массив b[A+1][B+1] изначально элементы которого равны 0.
Теперь с помощью ДП заполним значениями массив b[][] таким образом чтобы каждый элемент b[i][j] был равен количеству единиц в прямоугольнике с верхней левой координатой [0][0] и нижней правой [i][j] в массиве a[][].
C++
1
2
3
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
Теперь можно проходить по массиву b[][] и для каждого элемента b[i][j] опускаться вправо вниз осуществляя поиск максимального квадрата, заполненного только единицами:
C++
1
2
3
4
5
6
7
8
9
10
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        for(y=0; i+y<=A && j+y<=B; y++)
            if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
            {
                // вот здесь очередное значение площади квадрата полностью заполненное единицами равно (y+1)*(y+1)
                // сравниваете это значение с максимальным, если нужно меняете максимальное значение
            }
            else
                break;// значит в квадрате появился нолик (нолики)
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 8
Регистрация: 24.07.2012
Сообщений: 916
15.09.2012, 17:11     Найти квадратную матрицу из нулей #4
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Описание алгоритма (по моему быстрее не придумаешь):
создаем первый массив a[A+1][B+1], в котором нулевая строка и столбец заполнены нулями, а все остальное значениями из "чёрно-белого изображения размером A строк x B столбцов".
создаем второй массив b[A+1][B+1] изначально элементы которого равны 0.
Теперь с помощью ДП заполним значениями массив b[][] таким образом чтобы каждый элемент b[i][j] был равен количеству единиц в прямоугольнике с верхней левой координатой [0][0] и нижней правой [i][j] в массиве a[][].
C++
1
2
3
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
Теперь можно проходить по массиву b[][] и для каждого элемента b[i][j] опускаться вправо вниз осуществляя поиск максимального квадрата, заполненного только единицами:
C++
1
2
3
4
5
6
7
8
9
10
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        for(y=0; i+y<=A && j+y<=B; y++)
            if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
            {
                // вот здесь очередное значение площади квадрата полностью заполненное единицами равно (y+1)*(y+1)
                // сравниваете это значение с максимальным, если нужно меняете максимальное значение
            }
            else
                break;// значит в квадрате появился нолик (нолики)
я правильно понял, что Вы на кладываете квадратную " маску " на изображение и пытаетесь таким образом определить область квадратом? Если так , то если скажем это квадрат у которого края с "шумом" есть несколько белых точек вплотную со стороной области, разве будет такая область квадратом?

Я думал решать задачу так:
1) находить области с помощью рекурсии , либо итерационным алгоритмом поиска
2) создать временный контейнер для координат каждой области
3) на основании координат определять соотношение сторон , и если растояние между xmin xmax ,такое же как между ymin ymax то это квадрат
4) находим площади квадратов
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.09.2012, 17:20     Найти квадратную матрицу из нулей #5
Цитата Сообщение от Nixy Посмотреть сообщение
я правильно понял, что Вы на кладываете квадратную " маску " на изображение и пытаетесь таким образом определить область квадратом?
нет, не правильно поняли.
Здсеь идет такой расчет:
C++
1
if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
Если количество единиц в квадрате совпадает с общей площадью квадрата, то сравниваем значение с уже имеющимся максимальным, если не совпадает, то значит в квадрате уже имеются (имеется) нули (ноль)
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 17:25     Найти квадратную матрицу из нулей #6
А можно для маленьких областей как-то использовать тип long long - то есть приводить к нужному типу, а потом сравнивать числа? Я имею ввиду битовую арифметику. Правда больше 64 бит не получится проверить. Хотя можно проверять области,кратные 64 битам, и как-то их складывать..
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 8
Регистрация: 24.07.2012
Сообщений: 916
15.09.2012, 17:27     Найти квадратную матрицу из нулей #7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
нет, не правильно поняли.
Здсеь идет такой расчет:
C++
1
if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
Если количество единиц в квадрате совпадает с общей площадью квадрата, то сравниваем значение с уже имеющимся максимальным, если не совпадает, то значит в квадрате уже имеются (имеется) нули (ноль)
ну такое сравнение примерно и получается наложением готового квадрата, и если рядом будет еще отросток от него то такой алгоритм не проверит , хотя в постановке задачи явно и не сказано что квадрат должен быть чистым, над дождатся ТСа и у него спросить

Добавлено через 1 минуту
Цитата Сообщение от #pragma Посмотреть сообщение
А можно для маленьких областей как-то использовать тип long long - то есть приводить к нужному типу, а потом сравнивать числа? Я имею ввиду битовую арифметику. Правда больше 64 бит не получится проверить. Хотя можно проверять области,кратные 64 битам, и как-то их складывать..
Зачем это? Оо разве это надо в задаче?
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 17:31     Найти квадратную матрицу из нулей #8
Цитата Сообщение от Nixy Посмотреть сообщение
Зачем это? Оо разве это надо в задаче?
Ну так, наверное, было бы быстрее, мы как-бы проматывали бы кусками по 64 бита (по 2 элемента в массиве, если int 4 байта, и по 4 , если 2). Если не ошибся..
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.09.2012, 17:34     Найти квадратную матрицу из нулей #9
Цитата Сообщение от Nixy Посмотреть сообщение
ну такое сравнение примерно и получается наложением готового квадрата,
такое сравнение получается за O(n^2) где n размер квадрата, а приведенный алгоритм сразу вычисляет для каждого n количество единиц в нем (соответственно можно узнать - состоит из одних единиц или нет).

Цитата Сообщение от Nixy Посмотреть сообщение
хотя в постановке задачи явно и не сказано что квадрат должен быть чистым, над дождатся ТСа и у него спросить
да вроде как бы и не нужно:

Цитата Сообщение от OlegRuno Посмотреть сообщение
На чёрно-белом изображении размером A строк x B столбцов необходимо найти полностью белый квадрат с максимальной площадью.
Добавлено через 1 минуту
Цитата Сообщение от #pragma Посмотреть сообщение
Ну так, наверное, было бы быстрее, мы как-бы проматывали бы кусками по 64 бита (по 2 элемента в массиве, если int 4 байта, и по 4 , если 2). Если не ошибся..
в итоге будет медленнее
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 17:36     Найти квадратную матрицу из нулей #10
Цитата Сообщение от valeriikozlov Посмотреть сообщение
в итоге будет медленнее
А почему, можете прокомментировать?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.09.2012, 17:48     Найти квадратную матрицу из нулей #11
Цитата Сообщение от #pragma Посмотреть сообщение
А почему, можете прокомментировать?
Особых доводов нет, но:
Цитата Сообщение от OlegRuno Посмотреть сообщение
Размер изображения не превышает 1000 x 1000
Пусть именно такой начальный квадрат изначально есть. Вот представьте себе, я своим алгоритмом проверю все квадраты с левой верхней координатой [0][0] за 1000 итераций (их всего 1000 квадратов с левой верхней координатой [0][0]) , т.е. каждый квадрат сразу вычисляется (полностью заполнен единицами или нет). А Ваш алогритм каждый из этих 1000 квадратов будет проверять кусочками (сразу понятно, что будет медленнее). А если этот кусочек наполовину принадлежит проверяемому квадрату, а наполовину нет, что получится?
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 18:23     Найти квадратную матрицу из нулей #12
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Особых доводов нет, но:

Пусть именно такой начальный квадрат изначально есть. Вот представьте себе, я своим алгоритмом проверю все квадраты с левой верхней координатой [0][0] за 1000 итераций (их всего 1000 квадратов с левой верхней координатой [0][0]) , т.е. каждый квадрат сразу вычисляется (полностью заполнен единицами или нет). А Ваш алогритм каждый из этих 1000 квадратов будет проверять кусочками (сразу понятно, что будет медленнее). А если этот кусочек наполовину принадлежит проверяемому квадрату, а наполовину нет, что получится?
Хм, видимо, я условие не понял, мне казалось, что на входе матрица с максимальным размером 1000х1000, заполненная нулями и единицами, а не квадратными матрицами
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 8
Регистрация: 24.07.2012
Сообщений: 916
15.09.2012, 18:26     Найти квадратную матрицу из нулей #13
Цитата Сообщение от #pragma Посмотреть сообщение
Хм, видимо, я условие не понял, мне казалось, что на входе матрица с максимальным размером 1000х1000, заполненная нулями и единицами, а не квадратными матрицами
мне кажется valeriikozlov иммел ввиду , что изначально изображение все белое
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 19:29     Найти квадратную матрицу из нулей #14
Ок, я просто невнимательно прочитал, что все квадраты начинаются с [0][0]
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
15.09.2012, 20:34     Найти квадратную матрицу из нулей #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <memory.h>
#include <ctype.h>
 
#define A 10
#define B 12
 
typedef struct Coords
{
    int x0;
    int y0;
    int x1;
    int y1;
} COORDS;
 
bool exists(COORDS* p, int len, int i, int j)
{
    for (int n = 0; n < len; n++)
        if (i >= p[n].y0 && i <= p[n].y1 &&
            j >= p[n].x0 && j <= p[n].x1) 
            return true;
 
    return false;
}
 
int main()
{
    FILE* fp = NULL;
    const char* filename[2] = { "input.txt", "output.txt" };
    if ((fp = fopen(filename[0], "r")) == NULL)
    {
        printf("Unable to open file %s for reading\n",filename[0]);
        return 0;
    }
 
    int** Image = new int*[A];
    
    char line[256] = "\0";
    for (int t = 0; fgets(line, 256, fp) != NULL; t++)
    {
        Image[t] = new int[B]; int r = 0;
        for (int s = 0; line[s] != '\0'; s++)
            if (!isspace(line[s]) && isdigit(line[s]))
                Image[t][r++] = line[s] - '0';
    }
 
    fclose(fp);
 
    COORDS* coords = new COORDS[A*B];
    memset((void*)coords, 0x00, sizeof(COORDS) * A * B);
 
    COORDS field = { 0 };
    int q = 0, max_field = 0; 
    for (int i = 0; i < A; i++)
        for (int j = 0; j < B; j++)
            if (Image[i][j] == 1 && !exists(coords, q, i, j))
            {
                int d = i; bool bad_region = false;
                int width = 0, height = 0;
                while (Image[d][j] != 0 && !bad_region)
                {
                    int k = j;
                    while (Image[d][k] == 1) k++;
                    
                    if ((d > i) && abs(j-k) != width) bad_region = true; 
                    width = width <= 0 ? abs(j-k) : width;
 
                    d++; 
                }
 
                height = abs(i-d);
 
                if (bad_region == false)
                {
                    coords[q].x0 = j; coords[q].y0 = i;
                    coords[q].x1 = coords[q].x0 + width - 1;
                    coords[q].y1 = coords[q].y0 + height - 1;
 
                    if (width * height > max_field)
                    {
                        max_field = width * height;
                        field = coords[q];
                    }
 
                    q++;
                }
            }
 
    if ((fp = fopen(filename[1], "w")) == NULL)
    {
        printf("Unable to open file %s for writing\n",filename[1]);
        return 0;
    }
 
    fprintf(fp,"%d",max_field);
    fclose(fp);
 
    _getch();
 
    return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.09.2012, 07:15     Найти квадратную матрицу из нулей #16
OlegRuno, если будете реализовывать мой алгоритм, то вот эту часть:
C++
1
2
3
4
5
6
7
8
9
10
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        for(y=0; i+y<=A && j+y<=B; y++)
            if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
            {
                // вот здесь очередное значение площади квадрата полностью заполненное единицами равно (y+1)*(y+1)
                // сравниваете это значение с максимальным, если нужно меняете максимальное значение
            }
            else
                break;// значит в квадрате появился нолик (нолики)
можно значительно ускорить. Для этого нужно хранить и искать не максимальную площадь, а максимальную сторону квадрата (назовем ее L, изначально она равна -1).
Тогда основной проход будет выглядеть так:
C++
1
2
3
4
5
6
7
8
9
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        for(y=L+1; i+y<=A && j+y<=B; y++)
            if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
            {                
                L=y;
            }
            else
                break;// значит в квадрате появился нолик (нолики)
Вывод результата:
C++
1
(L+1)*(L+1);
OlegRuno
2 / 2 / 0
Регистрация: 28.05.2012
Сообщений: 38
17.09.2012, 19:37  [ТС]     Найти квадратную матрицу из нулей #17
Всем большое спасибо, 2 дня не было, приятно удивлен такому кол-ву ответов)

Добавлено через 5 часов 23 минуты
Другой вопрос парни) как считать то файл
вот пример, правильный ответ тут 9.
7 7
1101101
1111110
1011100
0011100
1000010
1100111
1001110

между цифрами нет пробелов(

Добавлено через 1 час 33 минуты
Всем большое спасибо, 2 дня не было, приятно удивлен такому кол-ву ответов)

Добавлено через 5 часов 23 минуты
Другой вопрос парни) как считать то файл
вот пример, правильный ответ тут 9.
7 7
1101101
1111110
1011100
0011100
1000010
1100111
1001110

между цифрами нет пробелов(
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.09.2012, 19:48     Найти квадратную матрицу из нулей #18
Цитата Сообщение от OlegRuno Посмотреть сообщение
Добавлено через 5 часов 23 минуты
Другой вопрос парни) как считать то файл
вот пример, правильный ответ тут 9.
7 7
1101101
1111110
1011100
0011100
1000010
1100111
1001110
между цифрами нет пробелов(
Можно например так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
 
int main()
{
      freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
    int x, y, i, j, **a;
    char str[1000];
    cin>>x>>y;
    a=new int*[x];
    for(i=0; i<x; i++)
    {
        a[i]=new int[y];
        cin>>str;
        for(j=0; j<y; j++)
            a[i][j]=(int)(str[j]-'0');
    }
    for(i=0; i<x; i++)
    {
        for(j=0; j<y; j++)
            cout<<a[i][j];
        cout<<endl;
    }
    
    return 0;
}
OlegRuno
2 / 2 / 0
Регистрация: 28.05.2012
Сообщений: 38
17.09.2012, 21:32  [ТС]     Найти квадратную матрицу из нулей #19
у меня не должно быть cin вообще

Добавлено через 2 минуты
все разобрался спасибо

Добавлено через 12 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
OlegRuno, если будете реализовывать мой алгоритм, то вот эту часть:
C++
1
2
3
4
5
6
7
8
9
10
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        for(y=0; i+y<=A && j+y<=B; y++)
            if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
            {
                // вот здесь очередное значение площади квадрата полностью заполненное единицами равно (y+1)*(y+1)
                // сравниваете это значение с максимальным, если нужно меняете максимальное значение
            }
            else
                break;// значит в квадрате появился нолик (нолики)
можно значительно ускорить. Для этого нужно хранить и искать не максимальную площадь, а максимальную сторону квадрата (назовем ее L, изначально она равна -1).
Тогда основной проход будет выглядеть так:
C++
1
2
3
4
5
6
7
8
9
for(i=1; i<=A; i++)
    for(j=1; j<=B; j++)
        for(y=L+1; i+y<=A && j+y<=B; y++)
            if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
            {                
                L=y;
            }
            else
                break;// значит в квадрате появился нолик (нолики)
Вывод результата:
C++
1
(L+1)*(L+1);
Объясните какими начальными данными инициируется L и y.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.09.2012, 06:11     Найти квадратную матрицу из нулей
Еще ссылки по теме:

C++ Сформировать квадратную матрицу
В матрице из нулей и единиц найти квадрат заданного размера, состоящую целиком из нулей C++
Матрица L(n,k) состоит из нулей и единиц. Найти в ней самую длинную цепочку подряд стоящих нулей по горизонтал C++
C++ В заданной матрице состоящей из нулей и единиц найти квадратную подматрицу, состоящую целиком из нулей
C++ Заполнить квадратную матрицу данными из файла и найти столбец с максимальной суммой элементов

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.09.2012, 06:11     Найти квадратную матрицу из нулей #20
Цитата Сообщение от OlegRuno Посмотреть сообщение
Объясните какими начальными данными инициируется L и y.
уже писал:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
назовем ее L, изначально она равна -1
Переменную y не нужно инициализировать в начале. Она используется только в цикле:
C++
1
for(y=L+1; i+y<=A && j+y<=B; y++)
Вот так пробуйте:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int i, j, y, L=-1, A, B, **b;
    char str[1000];
    cin>>A>>B;
    b=new int*[A+1];
    b[0]=new int[B+1];
    for(i=0; i<=B; i++) b[0][i]=0;
    for(i=1; i<=A; i++)
    {
        b[i]=new int[B+1];
        b[i][0]=0;
        cin>>str;
        for(j=1; j<=B; j++)
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+(str[j-1]-'0');
    }
    for(i=1; i<=A; i++)
        for(j=1; j<=B; j++)
            for(y=L+1; i+y<=A && j+y<=B; y++)
                if(b[i+y][j+y]-b[i-1][j+y]-b[i+y][j-1]+b[i-1][j-1]==(y+1)*(y+1))
                {                
                    L=y;
                }
                else
                    break;// значит в квадрате появился нолик (нолики)
    cout<<(L+1)*(L+1);  
    return 0;
}
Yandex
Объявления
18.09.2012, 06:11     Найти квадратную матрицу из нулей
Ответ Создать тему
Опции темы

Текущее время: 21:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru