Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 02.08.2019, 13:11   #1
Константин01
Пользователь
 
Регистрация: 11.05.2019
Сообщений: 21
По умолчанию Решение задачи из архива acmp (432)

Здравствуйте,

я решаю задачу 432 из архива acmp (http://acmp.ru/?main=task&id_task=432)

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

сейчас я решаю эту задачу с помощью системы непересекающихся множеств, однако имею некоторые проблемы с реализацией на C++

вкратце содержание кода:

1) считывает input, строит двухмерный массив
2) определяет стэк, куда складываются посещенные клетки при условии, что их значение равно единице.
3) в функции check происходит проверка тех клеток, которые принадлежат данной (по условию задачи - это окрестность фон Неймана первого порядка). Если клетка принадлежит - ее координаты - в стэк? а ее множество объединить с данной.
Пока стэк не пуст, повторять check()
4) Согласно идеи, в конце имеет массив p, где имеет повторяющиеся числа на позициях клеток, значение которых единица. Количество различных чисел на таких позициях и есть ответ на вопрос задачи.

Код:
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>

using namespace std;



void make_set(int p[], int x)
{
	p[x] = x;
}

int _find_set(int p[], int x)
{
	if (p[x] == x)
		return x;
	return p[x] = _find_set(p, p[x]);
}


int find_set(int p[], int m, int i, int j)
{
	int x;
	if (i==1)
		x = _find_set(p, i*j);
	else	
		x = _find_set(p, j+m);
	return x;
}

void unite_sets(int p[], int x, int y)
{
	x = _find_set(p, x);
	y = _find_set(p, y);
	if (x!=y)
	{
		p[y] = x;
	}
}

void check(vector< vector<int> > & g, int p[], int n, int m, stack< pair<int,int> > st)
{
	stack < pair<int,int> > s = st;
	int i = s.top().first;
	int j = s.top().second;
	s.pop();
	int x, y;
	x = find_set(p, m, i, j);
	if ( i > 1 )
	{
		y = find_set(p, m, i-1, j);
		if (g[i-1][j] == 1 && x!=y)
		{
			unite_sets(p, x, y);
			s.push({i-1, j});
		}
	}
	if ( j > 1 )
	{
		y = find_set(p, m, i, j-1);
		if (g[i][j-1] == 1 && x!=y)
		{
			unite_sets(p, x, y);
			s.push({i, j-1});
		}
	}
	if ( i+1 <= n )
	{
		if (g[i+1][j] == 1 && x!=y)
		{
			unite_sets(p, x, y);
			s.push({i+1, j});
		}
	}
	if ( j+1 <= m )
	{
		y = find_set(p, m, i, j+1);
		if (g[i][j+1] == 1 && x!=y)
		{
			unite_sets(p, x, y);
			s.push({i, j+1});
		}
	}
	if (!s.empty())
		check(g,p,n,m,s);
	else
		return;
}


int main()
{
	ifstream input("C:\\1\\input.txt");
	int n, m;
	int count = 0;
	input >> n, input >> m;
	vector< vector<int> > surface(n+1, vector<int>(m+1, 0));
	stack< pair<int,int> > stck;
	int p[n*m+1];
	for (int i=1; i<=n*m; i++)
		p[i] = i;
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			char val;
			input >> val;
			if (val == '#') surface[i][j] = 1;
		}
	}

	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			if (surface[i][j] == 1)
			{
				stck.push({i,j});
				check(surface, p, n, m, stck);
				stck.pop();
			}
		}
	}

	for (int i=1;i<=n*m;i++)
		cout << p[i] << ' ';

	return 0;

}
Проблема: сложно описать, в конце имеется массив p, где только первая часть содержит повторяющиеся числа.

Прошу проверить код на корректность.
Константин01 вне форума Ответить с цитированием
Старый 05.08.2019, 19:53   #2
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Она не так решается.
Формально - нужно найти количество компонент связности.
Вот и ищите. Запускайте дфс/бвс и все.
Никак dsu не надо
Dekay вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимизация (сокращение) кода решения задачи #2 c acmp.ru - нахождение суммы целых чисел от 1 до N Serge_Bliznykov Помощь студентам 31 23.08.2014 22:35
Решение задачи #71 на acmp.ru Poma][a Паскаль, Turbo Pascal, PascalABC.NET 9 28.08.2013 22:09
Оптимизация (сокращение) кода решения задачи #46 c acmp.ru - вывод числа E с заданной точностью Poma][a Паскаль, Turbo Pascal, PascalABC.NET 47 05.07.2013 23:50
Олимпиадные Задачи (с acmp.ru) Poma][a Паскаль, Turbo Pascal, PascalABC.NET 7 20.12.2012 07:44
Решение задачи l1merain Общие вопросы C/C++ 0 21.10.2011 18:29