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

Удары ферзем по фигурам!!! - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Поиск минимального, среднее и максимального чисел из трех введенных http://www.cyberforum.ru/cpp-beginners/thread176913.html
Помогите плиз, у пользователя запрашивают 3 числа и программа ищет среди них минимальное, среднее и максимальное. С++
C++ Нужен пример интерфейса Помагите нужен пример интерфейса на С++. В заранее благодарен. http://www.cyberforum.ru/cpp-beginners/thread176899.html
C++ Как написать ехе распаковку в dev c++
Помогите новичку написать ЕХЕ распаковку от нуля до конца. Ещё ЕХЕ не разу не писал и плохо знаю С++ (очень надо)
Сжать массив, удалив из него все элементы, модуль которых находится в интервале [a,b] C++
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1.) максимальный элемент массива; 2.) сумму элементов массива, расположенных до последнего положительного элемента. Сжать массив, удалив из него все элементы, модуль которых находится в интервале . Освободившиеся в конце массива элементы заполнить нулями. #include "stdafx.h" #include <conio.h> int main() { const...
C++ Массив заполняется случайными (не теми) элементами http://www.cyberforum.ru/cpp-beginners/thread176861.html
Доброго времени суток! Определенными циклами задаются значения массива. Циклы исправны (проверял в Паскале). Проблема в том, что в массиве вместо нужных значений в некоторых местах возникают числа типа 8000000000. Как с этим бороться? #include <conio.h> #include <stdlib.h> #include <math.h> #include <stdio.h> #include <iostream.h> //************ int main() {
C++ Найти количество слов в строке с использованием библиотечных функций string.h Найти количество слов в строке с использованием библиотечных функций string.h на языке С. Помогите Не дублируйте темы! подробнее

Показать сообщение отдельно
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
26.10.2010, 08:31     Удары ферзем по фигурам!!!
Цитата Сообщение от KuKu Посмотреть сообщение
Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов.
Для начала надо постоить взвешенный граф всех передвижений ферзя от одной фигуры к другой. Вершины графа - это поля на шахматной доске, где находятся фигуры или сам ферзь. Вес ребра в графе будет равен количеству шагов, которое ферзь должен сделать от поля одной вершины к другой. Сделаем это для твоего рисунка. Но сначала определим координаты фигур (в шахматной нотации):

ферзь: c2
фигуры: c5, c8, f3, f5

Вершины в нашем графе будут такие: c2, c5, c8, f3, f5.
Ребра:
c2-c5, вес=1
c2-c8, 1
c2-f3, 2 (нужно два шага)
c2-f5, 1
c5-c8, 1
c5-f3, 2
c5-f5, 1
c8-f3, 2
c8-f5, 1
f3-f5, 1

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

Но есть еще одна тонкость. Иногда таким образом будут находится неверные пути, т.е. ферзь с с2 на с8, перескакивая через с5. Поэтому в конце программы нужно проверять пути и отбрасывать неверные.
 
Текущее время: 21:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru