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

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

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

Аминь.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 15:56     Найти количество заштрихованых квадратов #7
Сетку можно рассматривать как граф: заштрихованные квадраты на сетке - это узлы графа, если 2 таких квадрата касаются друг друга стороной, то значит между ними есть ребро.
ваша задача сводится к поиску связных компонентов в графе (с помощью любого вида обхода графа DFS/BFS/PFS или с помощью disjoint set).
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 99
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
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 17:21     Найти количество заштрихованых квадратов #9
Цитата Сообщение от vozup Посмотреть сообщение
Вот что у меня получилось, но выдает число 7
1. сможете доказать корректность вашего алгоритма?
2. зачем циклы while если тело циклов всегда будет выполняться 1 раз?
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 99
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;
}
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 18:14     Найти количество заштрихованых квадратов #11
Цитата Сообщение от vozup Посмотреть сообщение
Никак не могу понять где ошибка, уже и по диагонали проверяю, все ровно не получается
почему вы думаете, что ваш алгоритм решает поставленную задачу?
но т.к. ответа на вопрос я от вас всё равно не дождусь, опишу следующую ситуацию:
есть фигура на сетке "3 заштрихованных квадрата в ряд (горизонтально)". Ваш алгоритм доходит до левого квадрата фигуры, увеличивает счетчик 1, обнуляет значение в соответствующей ячейке, а также обнуляет значение в ячейке левее. Далее идем к этой ячейке, которая левее, она имеет значение 0, следовательно пропускаем ее. Далее идем еще левее, к последнему квадрату фигуры. там стоит единица, следовательно увеличиваем счетчик на 1. Ошибка! счетчик не надо увеличивать, т.к. квадрат относится к уже помеченной фигуре.
Следовательно ваш алгоритм не решает задачу.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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 прилегающих к ней квадратов.
К тому же, проверять верхний, левый и верхний-левый квадраты смысла нет, так как по квадратам сверху и слева мы уже проходились циклом.
+ тут не учитывается выход за границы массива.
+ фигуру целиком ты так никогда не обнулишь - для этого нужен цикл или рекурсия, а то, что ты делаешь - это лишь обнуление восьми соседних клеток.
+ зачем их вообще проверять на заполненность, если ты мог записывать в них ноль вне зависимости от того, заполнена она или нет.
eocron
Кактус
 Аватар для 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;
}
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 99
20.08.2013, 13:38  [ТС]     Найти количество заштрихованых квадратов #14
Задача обновилась. Теперь нужно что бы при любых комбинациях выдавало правильное количество фигур
eocron
Кактус
 Аватар для 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 получишь количество фигур. (Задачки из МАИ ?)
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 99
20.08.2013, 15:54  [ТС]     Найти количество заштрихованых квадратов #16
Конечно спасибо, а нельзя ли как нибудь код попроще, просто если я принесу этот мне не поверят что я сделал))
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
20.08.2013, 16:05     Найти количество заштрихованых квадратов #17
С этой реализацией у вас больше шансов понять, что происходит. Берете листок в клеточку, рисуете 2 поля m * n, нумеруете от [0] до [m-1] / [n-1] грани этих полей. Первое поле - Ваше исходное поле, Второе поле - поле с вашими следами (грубо говоря на каждом шаге мы метим клеточку). Рисуете фигурки в первом поле и пошагово как в алгоритме, сами, ручками его выполняете, отмечая во втором поле ваши следы точечкой или крестиком.
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 99
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();
}
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
20.08.2013, 16:22     Найти количество заштрихованых квадратов #19
Да, все правильно, можно и так. Однако чаще всего бывают ситуации, когда размер поля не известен - его получают только в ходе выполнения программы. Если размер поля не изменяется вы все правильно сделали.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.08.2013, 16:28     Найти количество заштрихованых квадратов
Еще ссылки по теме:

Найти количество квадратов нечетных чисел среди компонент файла C++
C++ Вычислить количество цифр в заданном числе и сумму их квадратов
C++ Задача Robot. Найти количество единичных квадратов, на которых робот побывал более одного раза

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

Или воспользуйтесь поиском по форуму:
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 99
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;
Yandex
Объявления
20.08.2013, 16:28     Найти количество заштрихованых квадратов
Ответ Создать тему
Опции темы

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