Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
1

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

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

Author24 — интернет-сервис помощи студентам
Помогите решить задачку пожалуйста. Программа должна вывести количество заштрихованых квадратов (5) если квадраты прилегают друг к другу это щитается как 1.
Миниатюры
Найти количество заштрихованых квадратов  
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.08.2013, 14:32
Ответы с готовыми решениями:

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

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

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

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

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

Аминь.
1
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 15:56 7
Сетку можно рассматривать как граф: заштрихованные квадраты на сетке - это узлы графа, если 2 таких квадрата касаются друг друга стороной, то значит между ними есть ребро.
ваша задача сводится к поиску связных компонентов в графе (с помощью любого вида обхода графа DFS/BFS/PFS или с помощью disjoint set).
0
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
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
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 17:21 9
Цитата Сообщение от vozup Посмотреть сообщение
Вот что у меня получилось, но выдает число 7
1. сможете доказать корректность вашего алгоритма?
2. зачем циклы while если тело циклов всегда будет выполняться 1 раз?
0
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
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
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 18:14 11
Цитата Сообщение от vozup Посмотреть сообщение
Никак не могу понять где ошибка, уже и по диагонали проверяю, все ровно не получается
почему вы думаете, что ваш алгоритм решает поставленную задачу?
но т.к. ответа на вопрос я от вас всё равно не дождусь, опишу следующую ситуацию:
есть фигура на сетке "3 заштрихованных квадрата в ряд (горизонтально)". Ваш алгоритм доходит до левого квадрата фигуры, увеличивает счетчик 1, обнуляет значение в соответствующей ячейке, а также обнуляет значение в ячейке левее. Далее идем к этой ячейке, которая левее, она имеет значение 0, следовательно пропускаем ее. Далее идем еще левее, к последнему квадрату фигуры. там стоит единица, следовательно увеличиваем счетчик на 1. Ошибка! счетчик не надо увеличивать, т.к. квадрат относится к уже помеченной фигуре.
Следовательно ваш алгоритм не решает задачу.
0
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 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
Кактус
67 / 67 / 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
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
20.08.2013, 13:38  [ТС] 14
Задача обновилась. Теперь нужно что бы при любых комбинациях выдавало правильное количество фигур
0
Кактус
67 / 67 / 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
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
20.08.2013, 15:54  [ТС] 16
Конечно спасибо, а нельзя ли как нибудь код попроще, просто если я принесу этот мне не поверят что я сделал))
0
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
20.08.2013, 16:05 17
С этой реализацией у вас больше шансов понять, что происходит. Берете листок в клеточку, рисуете 2 поля m * n, нумеруете от [0] до [m-1] / [n-1] грани этих полей. Первое поле - Ваше исходное поле, Второе поле - поле с вашими следами (грубо говоря на каждом шаге мы метим клеточку). Рисуете фигурки в первом поле и пошагово как в алгоритме, сами, ручками его выполняете, отмечая во втором поле ваши следы точечкой или крестиком.
1
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
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
Кактус
67 / 67 / 19
Регистрация: 23.05.2012
Сообщений: 342
20.08.2013, 16:22 19
Да, все правильно, можно и так. Однако чаще всего бывают ситуации, когда размер поля не известен - его получают только в ходе выполнения программы. Если размер поля не изменяется вы все правильно сделали.
1
7 / 7 / 2
Регистрация: 25.12.2011
Сообщений: 111
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.08.2013, 16:28
Помогаю со студенческими работами здесь

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru