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

Задача "Солдатики" - C++

Восстановить пароль Регистрация
 
ruslawik
9 / 33 / 1
Регистрация: 25.05.2012
Сообщений: 113
26.10.2013, 09:41     Задача "Солдатики" #1
Описание

Вчера Арыстану подарили настольную игру. В эту игру входят набор солдатиков и доска размером 1000x1000. Правила игры таковы: вначале игры на некоторые различные клетки доски ставятся солдатики. Арыстан может выбрать одного солдатика и ходить им до тех пор, пока он не попадёт в клетку, в которой уже находится солдатик. Арыстан может за один ход двигать солдатика в любую соседнюю с нынешней клетку доски по вертикали, горизонтали или диагонали. Когда солдатик попадает в одну клетку с каким-либо другим солдатиком, тот, который уже стоял в той клетке доски, снимается с игры. После этого Арыстан может продолжить ходить тем же солдатиком, или же он может выбрать другого солдатика. Если Арыстан выбрал одного солдатика, он должен ходить им пока тот не попадет в одну клетку с другим солдатиком. Когда на доске остается один солдатик, игра заканчивается.
Друг Арыстана Биржан поставил на доске M солдатиков и задал Арыстану вопрос – за какое наименьшее количество ходов можно завершить игру. Помогите Арыстану ответить на этот вопрос.
Формат входных данных

В первой строке входного файла записано число M (M<=1000) – количество солдатиков. В следующих M строках записано по два числа xi и yi (xi , yi <=1000) – координаты клетки i-того солдатика. Гарантируется что все xi , yi попарно различны.
Формат выходных данных

Выведите одно число – наименьшее количество ходов за которое могла завершиться игра.



Input Output
5
1 1 6
1 3
3 2
4 1
4 3
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.10.2013, 09:41     Задача "Солдатики"
Посмотрите здесь:

Структуры... Задача: "База сотрудников небольшой фирмы" C++
Задача из книги "Програмирование - принцыпы и практика использования C++" C++
C++ Найти ошибку в решении "Числа - палиндрома" (задача с acmp)
C++ Задача "Гонки по улицам" (обход ориентированного графа)
Перевод из двоичной системы в десятичную, задача 2.30 "Как программировать на С++" C++
C++ Вычислить значение суммы. Задача с использованием "длинной арифметики".
Задача "Кто старше?" (подскажите где ошибка в коде) C++
Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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