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

Замок - обьясните задачу) - C++

Восстановить пароль Регистрация
 
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 285
27.09.2012, 23:55     Замок - обьясните задачу) #1
Доброго времени суток. Если кто может, прокомментриуйте пожалуйста код. Хочу разобраться в задаче и сделать сам. Предоставляю код моего друга. В самом низу условие есть.
Благодарю)

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<vector>
using namespace std;
 
int matrix[101][101],i,j,n,m,ans[101][101],paint=0,mask[4],square[10001];
 
void decode(int x)
{
    mask[0]=0;
    mask[1]=0;
    mask[2]=0;
    mask[3]=0;
    
    if(x>=8) 
    {
        mask[3]=1;
        x=x-8;
    }
    
    if(x>=4) 
    {
        mask[2]=1;
        x=x-4;  
    }
 
    if(x>=2) 
    {
        mask[1]=1;
        x=x-2;
    }
    if(x>=1) mask[0]=1;
 
}
 
 
void dfs(int x, int y)
{
    ans[x][y]=paint;
    square[paint]++;
    decode(matrix[x][y]);
    if ((mask[0]==0)&&(ans[x][y-1]==0)) dfs(x,y-1);
    decode(matrix[x][y]);
    if ((mask[1]==0)&&(ans[x-1][y]==0)) dfs(x-1,y);
    decode(matrix[x][y]);
    if ((mask[2]==0)&&(ans[x][y+1]==0)) dfs(x,y+1);
    decode(matrix[x][y]);
    if ((mask[3]==0)&&(ans[x+1][y]==0)) dfs(x+1,y);
}
 
 
 
 
int main()
{
    cin >> n >> m;
    for (i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            cin >> matrix[i][j];
            ans[i][j]=0;
        }
    for(i=1;i<=n*m;i++)
        square[i]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(ans[i][j]==0)
            {
                paint++;
                dfs(i,j);
            }
 
    for (i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }
    cout << "Total "<<paint<<" flats"<<endl;
    for(i=1;i<=paint;i++)
        cout<<"square of flat number "<<i<<" - "<<square[i]<<endl;
 
    int maxsq=0;
    int froom=0;
    int sroom=0;
 
    for(i=1;i<=n-1;i++)
        for(j=1;j<=m-1;j++)
        {
            if(square[ans[i][j]]!=square[ans[i][j+1]])
                if (square[ans[i][j]]+square[ans[i][j+1]]>maxsq)
                {
                    maxsq=square[ans[i][j]]+square[ans[i][j+1]];
                    froom=ans[i][j];
                    sroom=ans[i][j+1];
                }
            if(square[ans[i][j]]!=square[ans[i+1][j]])
                if (square[ans[i][j]]+square[ans[i+1][j]]>maxsq)
                {
                    maxsq=square[ans[i][j]]+square[ans[i+1][j]];
                    froom=ans[i][j];
                    sroom=ans[i+1][j];
                }
        }
 
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(ans[i][j]==sroom)
                ans[i][j]=froom;
 
    cout<<endl;
    
    if (froom!=0)
        cout<<"room "<<froom<<" and room "<<sroom<<" are united"<<endl;
 
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }
}
Вложения
Тип файла: doc Замок.doc (27.0 Кб, 29 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.09.2012, 23:55     Замок - обьясните задачу)
Посмотрите здесь:

обьясните код C++
C++ Обьясните.
Обьясните функцию C++
C++ Обьясните пожалуйста
C++ обьясните ошибку
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
28.09.2012, 00:02     Замок - обьясните задачу) #2
http://habrahabr.ru/post/113108/ Посмотрите часть про Двумерное динамическое программирование. Может оно
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
28.09.2012, 00:11     Замок - обьясните задачу) #3
вот это
Цитата Сообщение от DebieCooper Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void decode(int x)
{
 mask[0]=0;
 mask[1]=0;
 mask[2]=0;
 mask[3]=0;
if(x>=8) 
 {
 mask[3]=1;
 x=x-8;
 }
if(x>=4) 
 {
 mask[2]=1;
 x=x-4; 
 }
if(x>=2) 
 {
 mask[1]=1;
 x=x-2;
 }
 if(x>=1) mask[0]=1;
}
это установка значений в массив в зависимости от бит установленных в x
укладывается все в четыре строчки

C++
1
2
3
4
5
6
7
void decode(int x)
{
mask[0]=(int)(x&1==1);
 mask[1]=(int)(x&2==2);
 mask[2]=(int)(x&4==4);
 mask[3]=(int)(x&8==8);
}
непонятно зачем что нельзя работать с битовыми полями?

вот это очень "удобно" для понимания
Цитата Сообщение от DebieCooper Посмотреть сообщение
int matrix[101][101],i,j,n,m,ans[101][101],paint=0,mask[4],square[10001];
текст твой у меня не прочелся, не у всех стоят крутые навороченые офисы, конвертни хотя бы в 2003 или rtf
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 285
28.09.2012, 00:15  [ТС]     Замок - обьясните задачу) #4
Спасибо. Информация полезная. Но меня более интересует данный код. В особенности, что делает функция dfs. И буквально пару слов про то, что происходит в маине. По-мойму там где-то должен использовать поиск в глубину. Я про него пока не читал, завтра буду детальней разбираться.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
28.09.2012, 00:17     Замок - обьясните задачу) #5
DFS (Depth-first search) и есть поиск в глубину.
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 285
28.09.2012, 00:19  [ТС]     Замок - обьясните задачу) #6
ValeryS, спасибо. Но по-мойму функция decode как-то связана с стенами клетки. Т.е. северная клетка имеет значение 2, и т.д.
П.С. Не подскажите как там нужно конвертировать что?) Вроде ниразу ничего не конвертировал)
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
28.09.2012, 00:38     Замок - обьясните задачу) #7
Цитата Сообщение от DebieCooper Посмотреть сообщение
ValeryS, спасибо. Но по-мойму функция decode как-то связана с стенами клетки. Т.е. северная клетка имеет значение 2, и т.д.
ну и связана
массив то зачем заполнять
смотри
одна стена 1
вторая 2
третья 4
четвертая 8
это все степени двойки 0 1 2 3
в результате одна стена число 1 в двоичном коде 0001
первая и третья стена 5 в двоичном коде 0101
все стены 15 в двоичном коде 1111
изучи двоичную арифметику все понятней станет
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 285
28.09.2012, 19:15  [ТС]     Замок - обьясните задачу) #8
Благодарю. Постараюсь разобраться, если что - обращусь к вам

Добавлено через 18 часов 9 минут
Можете подробней рассказать про этот код, что оно как делает)
C++
1
2
3
4
5
6
7
void decode(int x)
{
mask[0]=(int)(x&1==1);
 mask[1]=(int)(x&2==2);
 mask[2]=(int)(x&4==4);
 mask[3]=(int)(x&8==8);
}
Добавлено через 5 минут
И про функцию dfs по-подробней.

Добавлено через 3 минуты
Вот что ,кстати, компилятор пишет на измененную функцию decode
C++
1
warning C4554: &: проверьте порядок применения операторов на наличие ошибки; для четкого задания порядка используйте скобки
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,040
28.09.2012, 20:16     Замок - обьясните задачу) #9
Цитата Сообщение от DebieCooper Посмотреть сообщение
Можете подробней рассказать про этот код, что оно как делает)
C++
1
2
3
4
5
6
7
void decode(int x)
{
mask[0]=(int)(x&1==1);
 mask[1]=(int)(x&2==2);
 mask[2]=(int)(x&4==4);
 mask[3]=(int)(x&8==8);
}
то же что и
Цитата Сообщение от DebieCooper Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void decode(int x)
{
 mask[0]=0;
 mask[1]=0;
 mask[2]=0;
 mask[3]=0;
if(x>=8) 
 {
 mask[3]=1;
 x=x-8;
 }
if(x>=4) 
 {
 mask[2]=1;
 x=x-4; 
 }
if(x>=2) 
 {
 mask[1]=1;
 x=x-2;
 }
 if(x>=1) mask[0]=1;
}
заполняет массив значениями в зависимости от флагов

например у тебя есть число 1 в двоичной форме 0001
проверяем первый флаг
mask[0]=(int)(x&1==1);
0001 & 0001 =0001
сравниваем
0001 и 0001 равны значит значение истина(1)
записываем в mask[0] 1
проверяем второй флаг
mask[1]=(int)(x&2==2);
0001 & 0010 =0000
сравниваем значения
0000 и 0010 неравны значит значение ложь(0)
записываем в mask[1] 0
ну итак далее по всем четырем флагам

Добавлено через 1 минуту
Цитата Сообщение от DebieCooper Посмотреть сообщение
warning C4554: &: проверьте порядок применения операторов на наличие ошибки; для четкого задания порядка используйте скобки
ну можно так
C++
1
2
3
4
5
6
7
void decode(int x)
{
mask[0]=(int)((x&1)==1);
 mask[1]=(int)((x&2)==2);
 mask[2]=(int)((x&4)==4);
 mask[3]=(int)((x&8)==8);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.09.2012, 00:05     Замок - обьясните задачу)
Еще ссылки по теме:

Обьясните программу C++
Обьясните запись C++
C++ Кодовый замок, срабатывание по условию

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

Или воспользуйтесь поиском по форуму:
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 285
29.09.2012, 00:05  [ТС]     Замок - обьясните задачу) #10
Спасибо большое, разобрался.
Можете еще обьяснить про функцию dfs? И можно ли, функцию dfs в другом виде записать, по проще если можно. Дальше я уже сам все сделаю.

Добавлено через 3 часа 32 минуты
Что-то я втуплять начал) Подскажите что делает
C++
1
square[paint]++;
, где paint=0.
Yandex
Объявления
29.09.2012, 00:05     Замок - обьясните задачу)
Ответ Создать тему
Опции темы

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