Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
#1

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

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

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

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

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

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

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

Найти количество квадратов, имеющих общую точку с прямой
В прямоугольной декартовой системе координат прямая задана двумя принадлежащими...

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

21
BigLow
55 / 55 / 6
Регистрация: 07.07.2013
Сообщений: 345
12.08.2013, 14:53 #2
C++
1
std::cout << 5;
2
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
12.08.2013, 15:10  [ТС] #3
Цитата Сообщение от BigLow Посмотреть сообщение
C++
1
std::cout << 5;
Как смешно!
0
Kuzia domovenok
2215 / 1984 / 447
Регистрация: 25.03.2012
Сообщений: 6,971
Записей в блоге: 1
12.08.2013, 15:14 #4
vozup, Ставь условие конкретно! Я уверен, задача звучала не так:
Цитата Сообщение от vozup Посмотреть сообщение
Помогите решить задачку пожалуйста. Программа должна вывести количество заштрихованых квадратов (5) если квадраты прилегают друг к другу это щитается как 1.
А, например, так:
Дана матрица m на n
Некоторые клетки в матрице заштрихованы, если их значение не равно 0
Фигурой будем называть группу всех клеток, прилегающих друг к другу по вертикали или горизонтали.
Найти количество квадратов в наибольшей фигуре.
0
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
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
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 15:56 #7
Сетку можно рассматривать как граф: заштрихованные квадраты на сетке - это узлы графа, если 2 таких квадрата касаются друг друга стороной, то значит между ними есть ребро.
ваша задача сводится к поиску связных компонентов в графе (с помощью любого вида обхода графа DFS/BFS/PFS или с помощью disjoint set).
0
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
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
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 17:21 #9
Цитата Сообщение от vozup Посмотреть сообщение
Вот что у меня получилось, но выдает число 7
1. сможете доказать корректность вашего алгоритма?
2. зачем циклы while если тело циклов всегда будет выполняться 1 раз?
0
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
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
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 18:14 #11
Цитата Сообщение от vozup Посмотреть сообщение
Никак не могу понять где ошибка, уже и по диагонали проверяю, все ровно не получается
почему вы думаете, что ваш алгоритм решает поставленную задачу?
но т.к. ответа на вопрос я от вас всё равно не дождусь, опишу следующую ситуацию:
есть фигура на сетке "3 заштрихованных квадрата в ряд (горизонтально)". Ваш алгоритм доходит до левого квадрата фигуры, увеличивает счетчик 1, обнуляет значение в соответствующей ячейке, а также обнуляет значение в ячейке левее. Далее идем к этой ячейке, которая левее, она имеет значение 0, следовательно пропускаем ее. Далее идем еще левее, к последнему квадрату фигуры. там стоит единица, следовательно увеличиваем счетчик на 1. Ошибка! счетчик не надо увеличивать, т.к. квадрат относится к уже помеченной фигуре.
Следовательно ваш алгоритм не решает задачу.
0
Kuzia domovenok
2215 / 1984 / 447
Регистрация: 25.03.2012
Сообщений: 6,971
Записей в блоге: 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 / 19
Регистрация: 23.05.2012
Сообщений: 342
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
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
20.08.2013, 13:38  [ТС] #14
Задача обновилась. Теперь нужно что бы при любых комбинациях выдавало правильное количество фигур
0
eocron
Кактус
66 / 66 / 19
Регистрация: 23.05.2012
Сообщений: 342
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
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
20.08.2013, 15:54  [ТС] #16
Конечно спасибо, а нельзя ли как нибудь код попроще, просто если я принесу этот мне не поверят что я сделал))
0
eocron
Кактус
66 / 66 / 19
Регистрация: 23.05.2012
Сообщений: 342
20.08.2013, 16:05 #17
С этой реализацией у вас больше шансов понять, что происходит. Берете листок в клеточку, рисуете 2 поля m * n, нумеруете от [0] до [m-1] / [n-1] грани этих полей. Первое поле - Ваше исходное поле, Второе поле - поле с вашими следами (грубо говоря на каждом шаге мы метим клеточку). Рисуете фигурки в первом поле и пошагово как в алгоритме, сами, ручками его выполняете, отмечая во втором поле ваши следы точечкой или крестиком.
1
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
20.08.2013, 16:14  [ТС] #18
А без указателей никак не обойтись, а то я сними пока еще не сильно дружу)

Добавлено через 2 минуты
Вот, я немножко переделал, не можете посмотреть правильный ли код?
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
#include <iostream>
#include <conio.h>
using namespace std;
 
const int n = 5, m = 5;
bool a[n][m];
bool flag[n][m];
 
 
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++)
        {
            if(check(i,j)) max++;
        }  
    }
    return max;
}
 
int main()
{
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            a[i][j] = 0;
            flag[i][j] = false;
        }
    }
 
        a[0][0+2] = a[0][1+2] = a[0][2+2] = a[0][3+2] = a[0][4+2] = 1;
        a[0+2][0] = a[0+2][1] = a[0+2][2] = a[0+2][3] = a[0+2][4] = 1;
        a[1][0] = a[1][2] = 1;
        a[4][3] = a[4][4] = 1;
 
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
           cout<<a[i][j]<<" ";
           cout<<endl;
    }
    
    cout<<max(n,m)<<endl;
    getch();
}
0
eocron
Кактус
66 / 66 / 19
Регистрация: 23.05.2012
Сообщений: 342
20.08.2013, 16:22 #19
Да, все правильно, можно и так. Однако чаще всего бывают ситуации, когда размер поля не известен - его получают только в ходе выполнения программы. Если размер поля не изменяется вы все правильно сделали.
1
vozup
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 103
20.08.2013, 16:28  [ТС] #20
Цитата Сообщение от eocron Посмотреть сообщение
Да, все правильно, можно и так. Однако чаще всего бывают ситуации, когда размер поля не известен - его получают только в ходе выполнения программы. Если размер поля не изменяется вы все правильно сделали.
Размеры полей это пока что временно, что бы вручную не набирать. А не могли бы вы еще объяснить вот этот код:
C++
1
2
3
4
int = check(i+1,j);
        res += check(i,j+1);
        res += check(i-1,j);
        res += check(i,j-1);
Здесь используется рекурсивная ф-я как я понимаю. Переменная res что она в себе хранит и почему по выходу возвращаем return res+1;
0
20.08.2013, 16:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.08.2013, 16:28
Привет! Вот еще темы с решениями:

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

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

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

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


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

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

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