Арифметика в квадрате
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Деревья и графы
- Строки
- Матрицы и сетки
Дан квадрат grid со стороной W (список из W строк по W символов). В каждой клетке стоит цифра 0–9, знак + или знак -, причём никакие две цифры и никакие два знака не соседствуют по горизонтали или вертикали.
Выражение строится так: начните в любой клетке с цифрой и шагайте в соседнюю клетку по горизонтали или вертикали, закончив снова на цифре. Выписанные по пути символы образуют выражение вида цифра знак цифра знак … цифра, которое вычисляется слева направо. Клетки можно посещать сколько угодно раз, в том числе сразу возвращаться назад.
Для каждого числа из списка queries найдите выражение с таким значением: самое короткое, а среди самых коротких — лексикографически наименьшее (символы сравниваются по кодам, поэтому + меньше -, а знаки меньше цифр). Верните список ответов в порядке запросов.
Ограничения: 2 ≤ W ≤ 8, 1 ≤ queries[i] ≤ 100, запросов до 30. Каждый запрос гарантированно достижим, и у нужного ответа значение после каждого числа (промежуточная сумма) не выходит за пределы −1000…1000.
Пример: ["2+1", "+4+", "5+1"], [2, 20] → ["2", "5+5+5+5"].
Источник: Coding Competitions Archive, codejam/2009/round_1b/square_math · © Google LLC · Apache-2.0 · условие переведено и дополнено