Ю4.26

TALVEZ-NOSSO-PERSONAGEM-NA-HISTRIA1Задача: На шахматной доске находятся король и несколько ферзей другого цвета. Проверить, находится ли король под угрозой и если да, кто ему угрожает. Положение фигур задано массивом A(8,8): 0 — клетка пуста, 1 — король, 2 — ферзь. Ферзь бьет по горизонтали, вертикали и диагоналям.

0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 2 0 0 0 2 2

Король под угрозой от ферзя на клетке (2,8) (по вертикали)

Король под угрозой от ферзя на клетке (8,2) (по горизонтали)

Король под угрозой от ферзя на клетке (8,8) (по диагонали)

Решение:

Ссылка на ideone C++: http://ideone.com/h4ECiW

Ссылка на ideone Java: http://ideone.com/sIJwPA

 

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

Калачьов Андрій Сергійович
Калачьов Андрій Сергійович

Latest posts by Калачьов Андрій Сергійович (see all)

13 thoughts on “Ю4.26

  1. Задача не самая простая из увиденных мной здесь. Что ж, тем интереснее будет решить ее правильно. 🙂
    Данный тест подскажет Вам две основные ошибки Вашего решения.

    0 0 0 0 0 0 0 0
    2 0 0 0 0 0 0 0
    0 2 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 2 0 0
    0 0 0 0 0 2 0 2

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

    • Либо можно сохранить всех потенциально бьющих ферзей в 4 массива — по каждому направлению, отсортировать их там и в каждом массиве выбрать не более двух ближайших к королю (с одной стороны и со второй). Это решение хорошо тем, что когда у нас доска 1е9 на 1е9, а ферзей — до 1е6, например (и задаются они уже перечислением), это решение работает, а проход во все стороны — ТЛЕшит.

      • Я понимаю про какой тайм лимит Вы говорите, но это касается принципиально другой задачи. Если задаются координаты фигур и их (m) много меньше чем линейный размер доски (n), то сортировка за m*log(m) окажется лучше чем О(n).
        Только в этой задаче формирование списков координат фигур займет O(n2) и общая сложность значительно превысит предложенный мной O(n).
        Нет?

        • Безусловно. Мое предложение состоит в том, чтобы потренировать более универсальный метод. Здесь разницы нет, но где-то она может проявить себя.

          • Согласен. Здесь всё равно. Поскольку сама задача ввода данных здесь уже имеет квадратичную сложность от линейного размера доски, ферзей на линиях можно и сортировать. Просто предложение использовать сортировку для нахождения минимума вызвало рефлекторный протест 🙂

Добавить комментарий