Heat Detector

Задача

Бэтмен

Речь пойдёт о первой задаче уровня Medium на сайте  codingame.com. По сюжету Бэтмен должен отыскать бомбу в многоэтажном доме. Ему известно количество этажей  и количество окон на каждом этаже. Ему также известно направление, в котором находится бомба. Бэтмену нужно как можно быстрее её найти. Процесс поиска выглядит следующим образом: Бэтмен заглядывает в какое-то окно и затем на каждом игровом шаге он перепрыгивает в какое-то другое окно — так до тех пор, пока не отыщет бомбу.

Инциализация

В первой строке заданы числа  W  и  H  —  соответственно количество окон на каждом этаже (оно для всех этажей одно и то же) и количество этажей в здании.

Во второй строке задано количество переходов, которые Бэтмен может сделать до взрыва. Это число нам не понадобится.

В третьей строке заданы два целых числа — x  и  y  —  координаты окна, с которого Бэтмен начинает свой поиск. Первая координата задаёт номер окна на этаже (начиная с нуля), вторая — номер этажа (также начиная с нуля). Нулевой этаж — верхний, нулевое окно на каждом этаже — левое.

Входные данные для одного игрового хода

Одна строка  DIR, задающая направление, в котором следует искать бобму:

Бэтмен3

Выходные данные для одного игрового хода

Одна строка, в которой заданы два целых числа, разделённых одним пробелом, — координаты окна, которое должен проверить Бэтмен.

Решение

Игровой цикл продолжается до тех пор, пока либо бобма взорвётся, либо Бэтмен её обезвредит. Т.е. либо нам не хватит шагов, либо мы угадаем обе координаты. На каждом шаге игрового цикла будем перемещать Бэтмена с учётом направления, в котором находится бомба, и при этом «сжимать» область игрового поля, в которой он может прыгать. Однажды этот промежуток ужмётся в ондну точку — ту самую, абсцисса которой соответствует координате бомбы.

Обозначим координаты бобмы через  BX  и  BY  и введём четыре вспомогательных параметра: l, r, u, b  —  «динамические границы», левая, правая, верхняя и нижняя соответственно. Идея состоит в том, чтобы на каждом шаге выполнялись неравенства  [latex] l \leq BX \leq r [/latex]  и  [latex] d \leq By \leq u [/latex].

Зададим начальные значения [latex] l = 0 [/latex],  [latex] r = W — 1 [/latex],   [latex] u = 0 [/latex]  и  [latex] d = H — 1 [/latex]. Тогда после инициализации игры указанные выше неравенства справедливы тривиальным образом (это просто заданные по условию ограничения на возможные значения  Bx  и  By). Переходим к первому ходу, он же первый шаг игрового цикла. Мы считали строку  DIR, указавшую нам направление, в котором следует искать бомбу.

Для оси абсцисс имеет место один из трёх случаев:

  • [latex] BX < x [/latex] (если DIR — одна из строк «L», «DL», «UL»). В этом случае справедливо неравенство  [latex] l \leq BX \leq x — 1 [/latex]. Положим  [latex] r = x — 1 [/latex]. Тогда будет справедливо неравенство  [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток  [latex] l \ldots r [/latex]  в этом случае будет на единицу короче предыдущего.
  • [latex] BX = x [/latex] (если DIR — одна из строк  «U»  и  «B»). В этом случае всё хорошо.
  • [latex] BX > x [/latex] (если  DIR — одна из строк  «R», «DR», «UR»). В этом случае справедливо неравенство  [latex] x + 1 \leq BX \leq r [/latex]. Положим  [latex] l = x + 1 [/latex]. Тогда будет справедливо неравенство  [latex] l \leq BX \leq r [/latex].  Отметим, что новый промежуток  [latex] l \ldots r [/latex]  в этом случае будет на единицу короче предыдущего.

Если  [latex] BX = x [/latex], то всё хорошо — мы уже знаем абсциссу бомбы. А что делать в остальных двух случаях? Как эффективнее искать бомбу? Можно просматривать все значения из промежутка [latex] l \ldots r [/latex] поочерёдно слева направо, но что если бомба расположена у правого края? Можно просматривать все значения поочерёдно справа налево, но что если координата бомбы равна  l, а промежуток большой? Остаётся один естественный вариант — «прыгнуть» в середину промежутка, т.е. в точку с абсциссой  [latex] \left \lfloor \frac{l + r}{2} \right \rfloor[/latex]. На следующем шаге цикла надо повторить приведённые выше рассуждения, изменения границ и «прыжок». Таким образом, либо мы случайно наткнётся на абсциссу бомбы, либо промежуток [latex] l .. r [/latex], уменьшаясь каждый раз на одно число,  ужмётся в точку, т.е. мы тоже найдём абсциссу бомбы! Осталось применить те же рассуждения к ординате бомбы. Надеюсь, код ответит на оставшиеся вопросы.

Код

Код на Java

 

Подтверждение

Бэтмен2

Heat Detector

Related Images:

6 thoughts on “Heat Detector

  1. Поскольку нам известно только направление, в котором следует производить поиск (и больше никакой информации о положении цели нет), я рассуждал так.

    На каждом шаге ограничиваем «допустимую область». При достаточно большой размере игрового поле она (область) условно может быть разбита на четыре примерно одинаковые части (назовём их квадрантами). В отсутствие дополнительное информации, считаем, что цель равновероятно может находиться в любой из этих четырёх частей. Поэтому я решил, что рациональнее всего не двигаться по ближайшему к нам квадранту, а прыгать в центр области.

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

  2. Пытаюсь попробовать переписать код на Java
    Си знаю плохо и не пойму для чего нам » DIR[0] » что оно делает?
    Это обращение к нулевому символу в строке?

    • Да.
      DIR это строка из одной или двух букв, которая показывает направление. В 26-й строке нужно определить, есть ли буква ‘L’ в строке DIR. В Java это делается так — if (DIR.indexOf('L') >=0) .... Аналогично делаете в 28-й строке. Дальше можно через charAt().
      Если хочется сделать так, как здесь, то вместо DIR[0] используйте DIR.charAt(0).

  3. До этого пробовал все сделать через charAt все
    if ((BOMB_DIR.charAt(0) == ‘L’) | (BOMB_DIR.charAt(1) == ‘L’))
    r = (X0 — 1);
    if ((BOMB_DIR.charAt(0) == ‘R’) | (BOMB_DIR.charAt(1) == ‘R’))
    l = (X0 + 1);
    if (BOMB_DIR.charAt(0) == ‘U’)
    d = (Y0 — 1);
    if (BOMB_DIR.charAt(0) == ‘D’)
    u = (Y0 + 1);
    int x = ((l + r)/2); // Абсцисса нового окна
    int y = ((u + d)/2); // Ордината нового окна
    System.out.println(x+» «+y);
    Выдавал ошибку такого содержания, но оставался на точке с координатами (3,5): Exception in thread «main» java.lang.StringIndexOutOfBoundsException: String index out of range: 1
    at java.lang.String.charAt on line 658
    at Player.main on line 30 (это как раз первая строчка кода)

    Сделал по вашему совету через indexOf а после оставил charAt
    теперь герой скачет между ячейками (3,5) и (1,5)
    if ((BOMB_DIR.indexOf(‘L’) >=0) | (BOMB_DIR.indexOf(‘L’) == 1) )
    r = X0 — 1;
    if ((BOMB_DIR.indexOf(‘R’) >=0) | (BOMB_DIR.indexOf(‘R’) == 1))
    l = X0 + 1;
    if (BOMB_DIR.charAt(0) == ‘U’)
    d = Y0 — 1;
    if (BOMB_DIR.charAt(0) == ‘D’)
    u = Y0 + 1;

    Я правильно вас понял?
    Или же что-то не то?
    Просто по-моему, лучше не стало)

  4. indexOf() ищет во всей строке. Зачем Вы каждую буквы ищете по два раза?
    Но это не должно повлиять на работу. Может Вы забыли в конце цикла вывести команду?
    На всякий случай проверил, всё работает и на Java. Кстати, этот метод называется «дихотомия»:

    P.S. Я добавил к коду два «else», но можно и без них.

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