С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.80/95: Рейтинг темы: голосов - 95, средняя оценка - 4.80
1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
1

Определить на сколько кусков распадётся клетчатый лист при удалаении заданных клеток

29.06.2018, 23:05. Показов 17488. Ответов 10
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Из прямоугольного листа клетчатой бумаги (N строк, M столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

В первой строке входного файла INPUT.TXT находятся целые числа N и M, в следующих N строках – по M символов (1 ≤ N, M ≤ 100). Если клетка не была вырезана, этому соответствует знак #, если вырезана – точка.

В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу.

Input:
4 8
#.##.#.#
......##
#.###.##
##.##.##

Output:
6
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.06.2018, 23:05
Ответы с готовыми решениями:

Из листа клетчатой бумаги размером М*Н клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа?
Срочно нужна помощь в выполнении данной задачи, т.к. в Паскале я полный 0. кому не сложно и есть...

Создать программу (Подсчитать, на сколько кусков распадется оставшаяся часть листа).
Из листа клетчатой бумаги размером M*K клеток удалили некоторые клетки. Подсчитать, на сколько...

Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? )
Доброго всем времени суток!! Помогите написать программу: Из листа клетчатой бумаги размером М*N...

На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм.
Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков...

10
11 / 9 / 11
Регистрация: 14.06.2017
Сообщений: 20
29.06.2018, 23:24 2
Когда-то давно решал эту задачку где-то здесь https://informatics.msk.ru/mod... pterid=652

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
#include <iostream>
#include <queue>
 
using namespace std;
 
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
int n, m, count=0;
bool matrix[100][100];
 
bool check(int y, int x){return ((0<=y) && (y<n) && (0<=x) && (x<m));}
 
void non_recursive_dfs(int start_y, int start_x){
    queue <int> queue_y, queue_x;
    queue_y.push(start_y);
    queue_x.push(start_x);
    int y, x;
   
    while(not queue_y.empty()){
        y = queue_y.front();
        x = queue_x.front();
        matrix[y][x] = 1;
        for(int i=0; i<4; i++)
            if(check(y+dy[i], x+dx[i]) and not matrix[y+dy[i]][x+dx[i]]){
                queue_y.push(y+dy[i]);
                queue_x.push(x+dx[i]);
            }
        queue_y.pop();
        queue_x.pop();
    }
}
 
int main(){
    cin >>n>>m;
   
    char ch;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++) {cin >>ch; matrix[i][j] = ch=='.';}
   
   
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(not matrix[i][j]){
                count++;
                non_recursive_dfs(i, j);
            }
   
    cout<<count;
   
    return 0;
}
1
1682 / 1095 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
30.06.2018, 14:49 3
Цитата Сообщение от Fortran Cobolov Посмотреть сообщение
void non_recursive_dfs
Это bfs же. Хотя задача легко решается как поиском в глубину так и поиском в ширину.
0
11 / 9 / 11
Регистрация: 14.06.2017
Сообщений: 20
30.06.2018, 15:12 4
Цитата Сообщение от Новичок Посмотреть сообщение
Это bfs же
Согласен. Однако dfs из этого кода несложно получить заменой очереди на стек. В этой задаче это не особо важно, т.к. все сводится к нахождению своеобразных компонент связности
0
1682 / 1095 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
30.06.2018, 16:57 5
Цитата Сообщение от Fortran Cobolov Посмотреть сообщение
Однако dfs из этого кода несложно получить заменой очереди на стек.
Да.
Цитата Сообщение от Fortran Cobolov Посмотреть сообщение
В этой задаче это не особо важно, т.к. все сводится к нахождению своеобразных компонент связности
Угу, об этом я уже писал выше.
0
1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
30.06.2018, 17:29  [ТС] 6
Новичок, я натыкалась на ваш ответ в теме Из листа клетчатой бумаги размером M умножить N клеток удалили некоторые клетки и там вы написали функцию, в которой надо было еще делать проверку на выход за границы массива и на то была ли посещена клетка. Я попробовала дописать, но оно как то не работает, можете указать на ошибки?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int x, int y) {
     visited[x][y] = true;
     for(int i = 0; i < n; i++)
     {
        for(int j = 0; j < m; j++)
        {
            if(!visited[i][j] && a[i][j] == '.' && (i >= 0 && j >= 0))
            dfs(i-1, j); // тут еще нужно проверять не выходим ли мы за границы массива 
            dfs(i+1, j); // и является ли эта клетка удаленной или посещенной
            dfs(i, j-1);
            dfs(i, j+1);
        }
     }
}
0
1682 / 1095 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
30.06.2018, 19:26 7
MHeming123345, тяжело тут указать на ошибки - подход неправильный. Зачем внутри dfs этот цикл? Проверка нужна не для i, j а для i-1, j; i+1, j и.т.д. А в мейне уже запустить dfs для всех клеток(которые не посещались еще и не были удалены) и после каждого вызова dfs увеличивать переменную-результат на 1.
0
1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
30.06.2018, 20:10  [ТС] 8
Новичок, то есть функция должна оставаться такой?
C++
1
2
3
4
5
6
7
8
9
void dfs(int x, int y) 
{
     visited[x][y] = true;
     if(a[x][y] == '.')
     dfs(x-1, y); 
     dfs(x+1, y); 
     dfs(x, y-1);
     dfs(x, y+1);
}
0
3 / 2 / 1
Регистрация: 29.10.2020
Сообщений: 28
13.07.2021, 23:00 9
Решение. Дфс в матрице, суть заключается в том, что просто идем в соседние вершины, проверяем и закрашиваем чтобы повторно туда не зайти. Количесво частей на которые распадется лист равно количеству компонент связности, а то есть количеству цветов в графе. Работает за О(n*m).
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
#include <bits/stdc++.h>
using namespace std;
int w[105][105];
int c[105][105];
int n, m;
 
void dfs(int i, int j) {
    if (w[i - 1][j] && !c[i - 1][j]) {
        c[i - 1][j] = c[i][j];
        dfs(i - 1, j);
    }
    if (w[i + 1][j] && !c[i + 1][j]) {
        c[i + 1][j] = c[i][j];
        dfs(i + 1, j);
    }
    if (w[i][j - 1] && !c[i][j - 1]) {
        c[i][j - 1] = c[i][j];
        dfs(i, j - 1);
    }
    if (w[i][j + 1] && !c[i][j + 1]) {
        c[i][j + 1] = c[i][j];
        dfs(i, j + 1);
    }
}
 
int main() {
    cin >> n >> m;
    char tmp;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> tmp;
            w[i][j] = (tmp == '#' ? 1 : 0);
        }
    }
 
    int color = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i][j] && !c[i][j]) {
                c[i][j] = color;
                dfs(i, j);
                color++;
            }
        }
    }
    cout << --color;
    return 0;
}
Код
1	Accepted	0,015	372 Кб
2	Accepted	0,015	372 Кб
3	Accepted	0,015	376 Кб
4	Accepted	0,015	376 Кб
5	Accepted	0,015	832 Кб
6	Accepted	0,03	716 Кб
7	Accepted	0,015	484 Кб
8	Accepted	0,015	588 Кб
9	Accepted	0,015	520 Кб
10	Accepted	0,015	368 Кб
11	Accepted	0,015	372 Кб
12	Accepted	0,015	380 Кб
1
3 / 3 / 0
Регистрация: 27.02.2022
Сообщений: 18
02.11.2022, 22:34 10
Один небольшой вопрос...
зачем? :
Цитата Сообщение от VyacheslavSqrt Посмотреть сообщение
int color = 1;
Цитата Сообщение от VyacheslavSqrt Посмотреть сообщение
cout << --color;
нельзя ли просто написать изначально
C++
1
int color = 0;
, а затем в ответе
C++
1
std::cout << color << std::endl;
???
Зачем все эти костыли в коде???



И да, если вы забыли, то итерация в массиве начинается с 0..

Добавлено через 7 минут
А нет, это я туплю. Прошу прощения))

Добавлено через 1 минуту
Но тот факт, что итерация начинается с 0, все равно остается)
0
3697 / 2647 / 761
Регистрация: 29.06.2020
Сообщений: 9,800
03.11.2022, 00:06 11
Цитата Сообщение от Oleg_Rodin Посмотреть сообщение
Но тот факт, что итерация начинается с 0, все равно остается
Это наверное рамка ограничитель, не зря же он массивы в статическую память положил, global scope.
От того что нет проверок на вводимые размеры, то это не совсем очевидно.
0
03.11.2022, 00:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.11.2022, 00:06
Помогаю со студенческими работами здесь

Из листа клетчатой бумаги N*N вырезали М клеток, на сколько кусков распадается оставшаяся часть листа?
условие:из листа клетчатой бумаги N*N клеток вырезали М клеток . на сколько кусков распадается...

Лена взяла клетчатый лист, нарисовала на нем прямоугольник размера n×3mn
Лена взяла клетчатый лист, нарисовала на нем прямоугольник размера n×3mn и начинает его заполнять...

Определить сколько клеток по периметру доски
Задача с условным оператором. В каждую крайнюю клетку квадратной доски поставили по фишке. Могло...

Определить, сколько значений f(x) при заданных x расположены выше и ниже указанной прямой
Цикл с предусловием. PascalAbc Значение функции f(x)=0,348+cos(x/4) определены при x=x0(hx)xn....


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

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