| Codeforces Round 221 (Div. 1) |
|---|
| Закончено |
Вам задана карта — прямоугольная таблица. Каждая клетка таблицы — это: либо препятствие, либо сокровище с определенной стоимостью, либо бомба, либо пустая клетка. Также задано ваше начальное положение.
Вы можете перейти из клетки в соседнюю по стороне клетку карты. При этом не разрешается выходить за пределы карты, приходить в клетки с сокровищами, препятствиями и бомбами. Для того, чтобы собрать сокровища, вы должны построить замкнутый путь (он должен начинаться и заканчиваться в стартовой клетке). Внутри этого замкнутого пути не должно быть клеток с бомбами. Пусть сумма стоимости сокровищ, находящихся внутри замкнутого пути, равна v, и при этом вы совершили k единичных переходов (из клетки в клетку), когда проходили этот путь, тогда такой путь принесет вам прибыль v - k рублей.
Ваша задача построить замкнутый путь, внутри которого не содержится бомб, который принесет наибольшую прибыль.
Обратите внимание, что путь может иметь самопересечения. Для определения того, лежит клетка внутри пути или нет используется следующий алгоритм:
- Представьте себе, что клетки таблицы — это точки на плоскости (клетка таблицы на пересечении i-го столбца и j-ой строки является точкой (i, j)). А заданный вам путь — это замкнутая ломаная, проходящая через эти точки.
- Вам нужно определить: находится ли точка p таблицы, через которую не проходит ломаная, внутри ломаной.
- Проведем луч, начинающийся в точке p и не проходящий через другие точки таблицы (такой луч обязательно существует).
- Посчитаем сколько отрезков ломаной пересекает проведенный луч. Если это количество нечетно, считается, что точка p (а следовательно и клетка таблицы) находится внутри ломаной (пути). Иначе, считается, что она находится снаружи.
В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 20) — размеры таблицы. Далее в n строках записано по m символов — описание таблицы. Расшифровка описания:
- символ «B» — обозначает клетку с бомбой;
- символ «S» — обозначает стартовую клетку, считается пустой клеткой;
- цифра c (1-8) — обозначает сокровище с индексом c;
- символ «.» — пустая клетка;
- символ «#» — препятствие.
Пусть на карте есть t сокровищ. Тогда далее в t строках заданы стоимости сокровищ. В i-ой строке задана стоимость сокровища с индексом i, vi ( - 200 ≤ vi ≤ 200). Гарантируется, что сокровища пронумерованы от 1 до t. Гарантируется, что всего на карте суммарно не более 8 объектов. Объектами считаются бомбы и сокровища. Гарантируется, что на карте ровно один символ «S».
Выведите одно целое число — максимально возможную прибыль, которую вы можете получить.
4 4
....
.S1.
....
....
10
2
7 7
.......
.1###2.
.#...#.
.#.B.#.
.3...4.
..##...
......S
100
100
100
100
364
7 8
........
........
....1B..
.S......
....2...
3.......
........
100
-100
100
0
1 1
S
0
В первом тестовом примере ответ будет выглядеть следующим образом.
Во втором тестовом примере ответ будет выглядеть следующим образом.
В третьем тесте прибыль нельзя получить.
В четвертом тесте прибыль нельзя получить, поскольку нельзя построить замкнутый путь более чем из одной клетки.
