С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
OlegRuno
2 / 2 / 0
Регистрация: 28.05.2012
Сообщений: 38
#1

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

15.09.2012, 15:50. Просмотров 1363. Ответов 19
Метки нет (Все метки)

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

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

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

В заданной матрице состоящей из нулей и единиц найти квадратную подматрицу, состоящую целиком из нулей - C++
Черный квадрат. В матрице состоящей из 0 и 1 найти квадрат заданного размера(квадратную подматрицу), состоящий целиком из нулей.

Заполнить квадратную матрицу данными из файла и найти столбец с максимальной суммой элементов - C++
Сама суть такова Программно сформировать файл data.txt содержащий 25 случайных чисел, записанных по 5 чисел в строке. Считать этот файл...

Сформировать квадратную матрицу; транспонировать матрицу и инвертировать порядок элементов каждой ее строки - C++
Заданы два одномерных массива одинаковой длины: R и S.Сформировать квадратную матрицу A, каждый элемент которой, что находится в i-той...

найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Нужно найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. В чем ошибка ? #include <iostream> #include...

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Здравствуйте, не могу понять в чём может быть ошибка :) Решаю олимпиадную задачу. Но система находит в тесте 5 не верный ответ) В...

В матрице из нулей и единиц найти квадрат заданного размера, состоящую целиком из нулей - C++
В матрице A (m, n), которая состоит из нулей и единиц, найти квадрат заданного размера (квадратную подматрицу), состоящую целиком из нулей ...

19
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
15.09.2012, 16:21 #2
Тебе нужен алгоритм поиска связнных областей? Есть два варианта один по проще , но требует память, другой по сложнее но не требует ее, тебе какой?
0
valeriikozlov
Эксперт С++
4676 / 2502 / 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;// значит в квадрате появился нолик (нолики)
0
Nixy
ComfyMobile
400 / 281 / 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) находим площади квадратов
0
valeriikozlov
Эксперт С++
4676 / 2502 / 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))
Если количество единиц в квадрате совпадает с общей площадью квадрата, то сравниваем значение с уже имеющимся максимальным, если не совпадает, то значит в квадрате уже имеются (имеется) нули (ноль)
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 17:25 #6
А можно для маленьких областей как-то использовать тип long long - то есть приводить к нужному типу, а потом сравнивать числа? Я имею ввиду битовую арифметику. Правда больше 64 бит не получится проверить. Хотя можно проверять области,кратные 64 битам, и как-то их складывать..
0
Nixy
ComfyMobile
400 / 281 / 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 битам, и как-то их складывать..
Зачем это? Оо разве это надо в задаче?
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 17:31 #8
Цитата Сообщение от Nixy Посмотреть сообщение
Зачем это? Оо разве это надо в задаче?
Ну так, наверное, было бы быстрее, мы как-бы проматывали бы кусками по 64 бита (по 2 элемента в массиве, если int 4 байта, и по 4 , если 2). Если не ошибся..
0
valeriikozlov
Эксперт С++
4676 / 2502 / 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). Если не ошибся..
в итоге будет медленнее
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 17:36 #10
Цитата Сообщение от valeriikozlov Посмотреть сообщение
в итоге будет медленнее
А почему, можете прокомментировать?
0
valeriikozlov
Эксперт С++
4676 / 2502 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.09.2012, 17:48 #11
Цитата Сообщение от #pragma Посмотреть сообщение
А почему, можете прокомментировать?
Особых доводов нет, но:
Цитата Сообщение от OlegRuno Посмотреть сообщение
Размер изображения не превышает 1000 x 1000
Пусть именно такой начальный квадрат изначально есть. Вот представьте себе, я своим алгоритмом проверю все квадраты с левой верхней координатой [0][0] за 1000 итераций (их всего 1000 квадратов с левой верхней координатой [0][0]) , т.е. каждый квадрат сразу вычисляется (полностью заполнен единицами или нет). А Ваш алогритм каждый из этих 1000 квадратов будет проверять кусочками (сразу понятно, что будет медленнее). А если этот кусочек наполовину принадлежит проверяемому квадрату, а наполовину нет, что получится?
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 18:23 #12
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Особых доводов нет, но:

Пусть именно такой начальный квадрат изначально есть. Вот представьте себе, я своим алгоритмом проверю все квадраты с левой верхней координатой [0][0] за 1000 итераций (их всего 1000 квадратов с левой верхней координатой [0][0]) , т.е. каждый квадрат сразу вычисляется (полностью заполнен единицами или нет). А Ваш алогритм каждый из этих 1000 квадратов будет проверять кусочками (сразу понятно, что будет медленнее). А если этот кусочек наполовину принадлежит проверяемому квадрату, а наполовину нет, что получится?
Хм, видимо, я условие не понял, мне казалось, что на входе матрица с максимальным размером 1000х1000, заполненная нулями и единицами, а не квадратными матрицами
0
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
15.09.2012, 18:26 #13
Цитата Сообщение от #pragma Посмотреть сообщение
Хм, видимо, я условие не понял, мне казалось, что на входе матрица с максимальным размером 1000х1000, заполненная нулями и единицами, а не квадратными матрицами
мне кажется valeriikozlov иммел ввиду , что изначально изображение все белое
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.09.2012, 19:29 #14
Ок, я просто невнимательно прочитал, что все квадраты начинаются с [0][0]
0
zitxbit
88 / 740 / 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;
}
1
15.09.2012, 20:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2012, 20:34
Привет! Вот еще темы с ответами:

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. Входные данные: В единственной строке...

Матрица L(n,k) состоит из нулей и единиц. Найти в ней самую длинную цепочку подряд стоящих нулей по горизонтал - C++
Помогите решить на C++ QtCreator

Задача на квадратную матрицу - C++
Дана целочисленная квадратная матрица. Определить: 1) Сумму элементов в тех столбцах, которые не содержат отрицательных элементов; 2)...

Упорядочить квадратную матрицу - C++
Упорядочить (отсортировать матрицу), что бы было так: a11 &lt;= a12 &lt;=&lt;= a1n &lt;= a21 &lt;= a22 &lt;=&lt;= a2n &lt;=&lt;= an1 &lt;= an1 &lt;=&lt;= ann Плюсом...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.