Королевский марш

Question

Вам дана шахматная доска с размером n x n. В нижнем правом квадрате доски, обозначенной символом s, есть король. Король должен достичь верхнего левого квадрата, отмеченного знаком e Остальные квадраты помечены либо целым числом p (обозначение точки), либо знаком x, обозначающим препятствие. Обратите внимание, что король может двигаться только вверх, влево и вверх влево (по диагонали). Найдите максимальное количество очков, которое может собрать король, и количество таких путей, которые может пройти король, чтобы сделать это.

Формат ввода Первая строка ввода состоит из целого числа t. Это количество тестов. Каждый тестовый пример содержит число n, которое обозначает размер доски. Далее следуют n строк, каждая из которых содержит n разделенных пробелами токенов.

Формат вывода Для каждого случая выведите в отдельной строке максимальное количество точек, которые можно собрать, и количество путей, доступных для обеспечения максимума, причем оба значения разделены пробелом. Если e недоступен из s, выведите 0 0.

Пример ввода

3
3
e 2 3
2 x 2
1 2 s
3
e 1 2
1 x 1
2 1 s
3
e 1 1
x x x
1 1 s

Пример вывода

7 1
4 2
0 0

Ограничение 1 <= t <= 100 </p>

2 <= n <= 200 </p>

1 <= p <= 9 </p>

Answer 1

Я думаю, что эту проблему можно решить с помощью динамического программирования. Мы могли бы использовать dp[i,j] для вычисления наилучшего количества баллов, которое вы можете получить, перейдя из правого нижнего угла в положение i,j. Мы можем вычислить dp[i,j] для действительного i,j на основе dp[i+1,j], dp[i,j+1] и dp[i+1,j+1], если это действительные позиции (не из матрицы или помечены как x), и суммировать их полученный в ячейке i,j. Вы должны начать вычисления с нижнего правого угла до левого верхнего, построчно и начиная с последнего столбца.

Для количества способов вы можете добавить новую матрицу ways и использовать ее для хранения количества способов.

Это пример кода, демонстрирующий идею:

dp[i,j] = dp[i+1,j+1] + board[i,j]
ways[i,j] = ways[i+1,j+1]

if dp[i,j] < dp[i+1,j] + board[i,j]:
   dp[i,j] = dp[i+1,j] + board[i,j]
   ways[i,j] = ways[i+1,j]

elif dp[i,j] == dp[i+1,j] + board[i,j]:
   ways[i,j] += ways[i+1,j]

# check for i,j+1

Это при условии, что все позиции действительны.

Окончательный результат сохраняется в dp[0,0] и ways[0,0].