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

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

Войти
Регистрация
Восстановить пароль
 
 
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 100
#1

Найти количество заштрихованых квадратов - C++

12.08.2013, 14:32. Просмотров 928. Ответов 21
Метки нет (Все метки)

Помогите решить задачку пожалуйста. Программа должна вывести количество заштрихованых квадратов (5) если квадраты прилегают друг к другу это щитается как 1.
0
Миниатюры
Найти количество заштрихованых квадратов  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.08.2013, 14:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти количество заштрихованых квадратов (C++):

В файле с целыми числами найти количество парных, количество удвоенных нечетных, количество квадратов нечетных - C++
Задано файл, компонентами которого являются целые числа. Найти: a) количество парных среди компонент файла; b) количество...

Найти количество квадратов размещенных на прямоугольнике - C++
Народ помогите с задачами на С. 1)Даны целые положительные числа A, B, C. На прямоугольнике размера A × B размещено максимально возможное...

Найти количество квадратов из единиц в двумерном массиве - C++
Добрый день. Я начинающий программист. Решаю задачки и вот столкнулся с такой пробл.: Почему при вводе данных: 1 - кол-во...

Найти количество квадратов в наборе из 10 целых положительных чисел - C++
Описать функцию IsSquare(K) логического типа, возвращающую True, если целый параметр K (> 0) является квадратом некоторого целого числа, и...

Найти количество квадратов, имеющих общую точку с прямой - C++
В прямоугольной декартовой системе координат прямая задана двумя принадлежащими ей точками (О, W) и (100N, Е). Также заданы N2 квадратов со...

Найти количество квадратов нечетных чисел среди компонент файла - C++
Дан файл f, компоненты которого являются целыми числами. Найти количество квадратов нечетных чисел среди компонент файла. Помогите...

21
BigLow
55 / 55 / 2
Регистрация: 07.07.2013
Сообщений: 345
12.08.2013, 14:53 #2
C++
1
std::cout << 5;
2
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 100
12.08.2013, 15:10  [ТС] #3
Цитата Сообщение от BigLow Посмотреть сообщение
C++
1
std::cout << 5;
Как смешно!
0
Kuzia domovenok
1950 / 1803 / 139
Регистрация: 25.03.2012
Сообщений: 6,245
Записей в блоге: 1
12.08.2013, 15:14 #4
vozup, Ставь условие конкретно! Я уверен, задача звучала не так:
Цитата Сообщение от vozup Посмотреть сообщение
Помогите решить задачку пожалуйста. Программа должна вывести количество заштрихованых квадратов (5) если квадраты прилегают друг к другу это щитается как 1.
А, например, так:
Дана матрица m на n
Некоторые клетки в матрице заштрихованы, если их значение не равно 0
Фигурой будем называть группу всех клеток, прилегающих друг к другу по вертикали или горизонтали.
Найти количество квадратов в наибольшей фигуре.
0
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 100
12.08.2013, 15:28  [ТС] #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
vozup, Ставь условие конкретно! Я уверен, задача звучала не так:А, например, так:
Дана матрица m на n
Некоторые клетки в матрице заштрихованы, если их значение не равно 0
Фигурой будем называть группу всех клеток, прилегающих друг к другу по вертикали или горизонтали.
Найти количество квадратов в наибольшей фигуре.
Нет, нужно найти количество этих фигур
0
Ch1or
76 / 17 / 1
Регистрация: 03.02.2013
Сообщений: 52
12.08.2013, 15:56 #6
Создаете двухмерный массив размером *ширина х длина*, подстать таблице с кубиками. Заполняете элементы массива, соответствующие заштрихованным кубикам единицами остальное -нулями. Создаете счетчик, пробегаетесь по массиву, в случае обнаружения элемента равного 1 увеличиваете счетчик на 1 и ставите его равным 0 проверяете все элементы вокруг этого счетчика (только по вертикали и горизонтали) и если хоть один из них равен 1 не трогаете счетчик, а просто обнуляете данный элемент. Далее просто выводим счетчик на экран.

Аминь.
1
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 15:56 #7
Сетку можно рассматривать как граф: заштрихованные квадраты на сетке - это узлы графа, если 2 таких квадрата касаются друг друга стороной, то значит между ними есть ребро.
ваша задача сводится к поиску связных компонентов в графе (с помощью любого вида обхода графа DFS/BFS/PFS или с помощью disjoint set).
0
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 100
12.08.2013, 16:57  [ТС] #8
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
#include "stdafx.h"
#include <windows.h>
#include <iostream>
#include <conio.h>
using namespace std;
 
 
int main()
{
    int i,j,s = 2;
    int mass[9][7];
    int summa = 0;
for(i=0;i<9;i++)//рядок
{
    for(j=0;j<7;j++)//столбец
        mass[i][j] = 0;
        mass[0][0] = mass[0][1] = mass[0][2] = 1;
        mass[1][0] = mass[1][2] = 1;
        mass[4][3] = mass[4][4] = 1;
        mass[5][4] = mass[5][6] = 1;
        mass[6][6] = 1;
        mass[7][1] = 1;
        mass[8][4] = mass[8][5] = 1;
}
for(i=0;i<9;i++)//рядок
{
    for(j=0;j<7;j++)//столбец
        cout<<mass[i][j]<<" ";
        cout<<endl;
}
for(i=0;i<9;i++)//рядок
{
    for(j=0;j<7;j++)//столбец
        if(mass[i][j])
        {
            summa ++;
            mass[i][j] = 0;
            while(mass[i][j+1]) 
            {
                mass[i][j+1]=0;
            }
            while(mass[i+1][j])
            {
                mass[i+1][j]=0;
            }
            while(mass[i][j-1]) 
            {
                mass[i][j-1]=0;
            }
            while(mass[i-1][j])
            {
                mass[i-1][j]=0;
            }
        }
}
 
cout<<"\n\n"<<summa<<"\n\n";
 
    getch();
    return 0;
}
Вот что у меня получилось, но выдает число 7
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 17:21 #9
Цитата Сообщение от vozup Посмотреть сообщение
Вот что у меня получилось, но выдает число 7
1. сможете доказать корректность вашего алгоритма?
2. зачем циклы while если тело циклов всегда будет выполняться 1 раз?
0
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 100
12.08.2013, 17:55  [ТС] #10
Никак не могу понять где ошибка, уже и по диагонали проверяю, все ровно не получается
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
#include "stdafx.h"
#include <windows.h>
#include <iostream>
#include <conio.h>
using namespace std;
 
 
int main()
{
    int i,j,s = 2;
    int mass[9][7];
    int summa = 0;
for(i=0;i<9;i++)//рядок
{
    for(j=0;j<7;j++)//столбец
        mass[i][j] = 0;
        mass[0][0] = mass[0][1] = mass[0][2] = 1;
        mass[1][0] = mass[1][2] = 1;
        mass[4][3] = mass[4][4] = 1;
        mass[5][4] = mass[5][6] = 1;
        mass[6][6] = 1;
        mass[7][1] = 1;
        mass[8][1] = mass[8][4] = mass[8][5] = 1;
}
for(i=0;i<9;i++)//рядок
{
    for(j=0;j<7;j++)//столбец
        cout<<mass[i][j]<<" ";
        cout<<endl;
}
for(i=0;i<9;i++)//рядок
{
    for(j=0;j<7;j++)//столбец
        if(mass[i][j])
        {
            summa ++;
            mass[i][j] = 0;
            if(mass[i][j+1]) //правый
            {
                mass[i][j+1]=0;
            }
            if(mass[i+1][j])//нижний
            {
                mass[i+1][j]=0;
            }
            if(mass[i-1][j])//верхний
            {
                mass[i-1][j]=0;
            }
            if(mass[i][j-1]) //левый
            {
                mass[i][j-1]=0;
            }
            if(mass[i+1][j-1]) //диаг левый низ
            {
                mass[i+1][j-1]=0;
            }
            if(mass[i+1][j+1]) //диаг правый низ
            {
                mass[i+1][j+1]=0;
            }
            if(mass[i-1][j-1]) //диаг левый верх
            {
                mass[i-1][j-1]=0;
            }
            if(mass[i-1][j+1]) //диаг левый верх
            {
                mass[i-1][j+1]=0;
            }
        }
}
 
 
 
cout<<"\n\n"<<summa<<"\n\n";
 
    getch();
    return 0;
}
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 18:14 #11
Цитата Сообщение от vozup Посмотреть сообщение
Никак не могу понять где ошибка, уже и по диагонали проверяю, все ровно не получается
почему вы думаете, что ваш алгоритм решает поставленную задачу?
но т.к. ответа на вопрос я от вас всё равно не дождусь, опишу следующую ситуацию:
есть фигура на сетке "3 заштрихованных квадрата в ряд (горизонтально)". Ваш алгоритм доходит до левого квадрата фигуры, увеличивает счетчик 1, обнуляет значение в соответствующей ячейке, а также обнуляет значение в ячейке левее. Далее идем к этой ячейке, которая левее, она имеет значение 0, следовательно пропускаем ее. Далее идем еще левее, к последнему квадрату фигуры. там стоит единица, следовательно увеличиваем счетчик на 1. Ошибка! счетчик не надо увеличивать, т.к. квадрат относится к уже помеченной фигуре.
Следовательно ваш алгоритм не решает задачу.
0
Kuzia domovenok
1950 / 1803 / 139
Регистрация: 25.03.2012
Сообщений: 6,245
Записей в блоге: 1
12.08.2013, 18:16 #12
Цитата Сообщение от vozup Посмотреть сообщение
Никак не могу понять где ошибка, уже и по диагонали проверяю, все ровно не получается
да сам подход неверный.
Насколько я понимаю твой алгоритм,
-ты проходишь по всем клеткам.
-при обнаружении заштрихованной увеличиваешь счётчик
- ну и пытаешься обнулить всю фигуру, которой клетка принадлежит, чтобы счётчик срабатывал единожды на одну фигуру.
только обнуление фигуры у тебя вообще бредовое!
вот это
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
 if(mass[i][j+1]) //правый
            {
                mass[i][j+1]=0;
            }
            if(mass[i+1][j])//нижний
            {
                mass[i+1][j]=0;
            }
            if(mass[i-1][j])//верхний
            {
                mass[i-1][j]=0;
            }
            if(mass[i][j-1]) //левый
            {
                mass[i][j-1]=0;
            }
            if(mass[i+1][j-1]) //диаг левый низ
            {
                mass[i+1][j-1]=0;
            }
            if(mass[i+1][j+1]) //диаг правый низ
            {
                mass[i+1][j+1]=0;
            }
            if(mass[i-1][j-1]) //диаг левый верх
            {
                mass[i-1][j-1]=0;
            }
            if(mass[i-1][j+1]) //диаг левый верх
            {
                mass[i-1][j+1]=0;
            }
обнулит не всю фигуру, а лишь 8 прилегающих к ней квадратов.
К тому же, проверять верхний, левый и верхний-левый квадраты смысла нет, так как по квадратам сверху и слева мы уже проходились циклом.
+ тут не учитывается выход за границы массива.
+ фигуру целиком ты так никогда не обнулишь - для этого нужен цикл или рекурсия, а то, что ты делаешь - это лишь обнуление восьми соседних клеток.
+ зачем их вообще проверять на заполненность, если ты мог записывать в них ноль вне зависимости от того, заполнена она или нет.
0
eocron
Кактус
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
12.08.2013, 19:38 #13
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
#include <vector>
#include <iostream>
using namespace std;
 
bool **a;
bool **flag;
 
 
int check(int i, int j)
{
    if(a[i][j] && !flag[i][j])
    {
        flag[i][j] = true;
        int res = check(i+1,j);
        res += check(i,j+1);
        res += check(i-1,j);
        res += check(i,j-1);
        return res+1;
    }
    return 0;
}
 
int max(int n, int m)
{
    int max = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int buf = check(i,j);
            max = (max < buf)? buf : max;
        }  
    }
    return max;
}
 
int main()
{
    int n, m;
    cin>> n;
    cin>> m;
    
    flag = new bool*[n];
    a = new bool*[n];
    
    for(int i=0;i<n;i++)
    {
        flag[i] = new bool[m];
        a[i] = new bool[m];
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
            flag[i][j] = false;
        }
    }
    
    cout<<max(n,m)<<endl;
}
1
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 100
20.08.2013, 13:38  [ТС] #14
Задача обновилась. Теперь нужно что бы при любых комбинациях выдавало правильное количество фигур
0
eocron
Кактус
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
20.08.2013, 13:54 #15
C++
1
2
3
 
int buf = check(i,j);
max = (max < buf)? buf : max;
замени на:

C++
1
if(check(i,j)) max++;
Тогда на выходе функции max получишь количество фигур. (Задачки из МАИ ?)
1
20.08.2013, 13:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.08.2013, 13:54
Привет! Вот еще темы с ответами:

Найти количество квадратов нечётных чисел среди компонентов файла - C++
Помогите, пожалуйста) Заполнить файл f натуральными числами, полученными с помощью генератора случайных чисел. Найти количество квадратов...

Задача Robot. Найти количество единичных квадратов, на которых робот побывал более одного раза - C++
Задача Robot. Робот находится на плоскости, которая разбита на единичные квадраты. Робот может двигаться в четырех направлениях на...

Посчитать количество получившихся квадратов - C++
Квадраты Ограничения: время – 1s/Java 2s, память – 8MiB На уроке труда всем раздали по прямоугольнику со сторонами размером A и B...

В массиве записаны оценки, найти количество пятерок, количество четверок, количество троек и количество двоек - C++
В массиве записаны оценки по иностранному языку каждого из 22 учеников класса. Определить количество пятерок, количество четверок,...


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

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

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