Увидел следующую загадку на HN и подумал, что я сделаю репост здесь.Это можно решить с помощью Simplex, но мне было интересно, есть ли более элегантное решение или кто-то может доказать NP-полноту.
Каждая точка ниже представляет положение лазера.Укажите направление, в котором должен срабатывать лазер, заменив точку на ^, v, <или>.Каждая позиция сетки i, j должна быть поражена точно сеточными [i] [j] лазерами.В приведенном ниже примере позиция сетки 0,0 должна быть поражена точно сеткой [0] [0] = 2 лазера.
Лазер проходит через все на своем пути, включая другие пушки (без уничтожения этих пушек).
2 2 3 . 1 . 2 2 3
1 . 2 1 1 . 1 . 2
2 3 . 1 . 2 . 4 .
. 3 . 2 2 . 2 3 4
1 . 2 . 2 3 2 . .
2 3 . 3 . 3 2 2 .
3 . 2 4 2 . 2 . 2
1 1 . . 1 3 . 2 .
. 2 1 . 2 . 1 . 3