Шахматная доска, расстояние от начальной до заданной точки, некоторые клетки заняты фигурами

@gromil · Регистрация: 26.12.2009

Студворк — интернет-сервис помощи студентам

На шахватной доске (не обязательно 8х8) стоит ферзь. Нужно определить, за сколько ходов он может добраться в заданную точку, если известны координаты начальной и заданной точки. НО дело в том, что некоторые клетки заняты фигурами, но в данный момент они не могут ходить(наверное спят

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

Я так это представляю, как графы, где уместно и рационально использовать поиск в ширину, но не могу вбить в код и еще пометить вершины недоступными(спящие фигуо=ры), вот моя проблема, прошу помочь

@pikusfikus · 01.01.2010, 15:45

это задача с Netol2009

@gromil · 01.01.2010, 23:24 **[ТС]**

прошу прощения, я не знаю, что это и нам дали это на защиту, это, я так понял, как-йто туринр, прошу прощения, все-таки лучше самому решать)

@pikusfikus · 01.01.2010, 23:28

даю подсказку,это некоторая модификация волнового алгоритма.у меня есть эта задача ,но увы я на турнире,не хочу помогать конкуренту )

@odip · 02.01.2010, 08:59

Не знаю с турнира задача или нет - но задача простая.
Поле делаем в виде матрицы 8x8.
В начале помечаем все поля как недостижимые.
Помечаем все поля со фигурами.
Заводим очередь ходов.
В начале в очередь помещаем начальную клетку и число ходов 0.

А дальше волновой алгоритм.
Извлекаем из очереди очередную клетку.
Помечаем клетку в матрице.
Далее делаем ходы ферзем по полю, все ходы записываем в очередь с числом ходов +1.

Нужно учитывать что если мы пришли в какую-то клетку поля, то до этой клетки может быть несколько путей. Мы должны из всех путей записывать минимальное число ходов.

Алгоритм завершается когда очередь пуста.

После чего смотрим сколько ходов указано в матрице в конечной клетке.
Может так получиться, что конечная клетка недостижима - заставлена фигурами.

@pikusfikus · 02.01.2010, 14:10

Сообщение от odip

Не знаю с турнира задача или нет - но задача простая.
Поле делаем в виде матрицы 8x8.

а почему поле 8х8 там же указано что может быть больше

@odip · 03.01.2010, 06:57

Ну делаем больше чем 8x8 - это не принципиально.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@gromil 2 / 2 / 4 Регистрация: 26.12.2009 Сообщений: 70

	Шахматная доска, расстояние от начальной до заданной точки, некоторые клетки заняты фигурами 01.01.2010, 14:59. Показов 1557. Ответов 6 Метки нет (Все метки) На шахватной доске (не обязательно 8х8) стоит ферзь. Нужно определить, за сколько ходов он может добраться в заданную точку, если известны координаты начальной и заданной точки. НО дело в том, что некоторые клетки заняты фигурами, но в данный момент они не могут ходить(наверное спят ) Итак, вводяться координаты начальной и заданной точки и координаты спящих фигур, надо определить,за какой мин. кол-во ходов ферзь добереться в заданную точку. Я так это представляю, как графы, где уместно и рационально использовать поиск в ширину, но не могу вбить в код и еще пометить вершины недоступными(спящие фигуо=ры), вот моя проблема, прошу помочь 0

@pikusfikus 175 / 172 / 40 Регистрация: 14.11.2009 Сообщений: 507
	01.01.2010, 15:45
	это задача с Netol2009 0

@gromil 2 / 2 / 4 Регистрация: 26.12.2009 Сообщений: 70
	01.01.2010, 23:24 [ТС]
	прошу прощения, я не знаю, что это и нам дали это на защиту, это, я так понял, как-йто туринр, прошу прощения, все-таки лучше самому решать) 0

@pikusfikus 175 / 172 / 40 Регистрация: 14.11.2009 Сообщений: 507
	01.01.2010, 23:28
	даю подсказку,это некоторая модификация волнового алгоритма.у меня есть эта задача ,но увы я на турнире,не хочу помогать конкуренту ) 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	02.01.2010, 08:59
	Не знаю с турнира задача или нет - но задача простая. Поле делаем в виде матрицы 8x8. В начале помечаем все поля как недостижимые. Помечаем все поля со фигурами. Заводим очередь ходов. В начале в очередь помещаем начальную клетку и число ходов 0. А дальше волновой алгоритм. Извлекаем из очереди очередную клетку. Помечаем клетку в матрице. Далее делаем ходы ферзем по полю, все ходы записываем в очередь с числом ходов +1. Нужно учитывать что если мы пришли в какую-то клетку поля, то до этой клетки может быть несколько путей. Мы должны из всех путей записывать минимальное число ходов. Алгоритм завершается когда очередь пуста. После чего смотрим сколько ходов указано в матрице в конечной клетке. Может так получиться, что конечная клетка недостижима - заставлена фигурами. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	03.01.2010, 06:57
	Ну делаем больше чем 8x8 - это не принципиально. 0