| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 13 | 1 | 1 | 7.692% |
Люк Скайуокер ступил на скользкий путь! К счастью, его не влечет Темная сторона. Он всего лишь оказался на планете Хот, целиком покрытой снегом и льдом, потому передвигаться по местности необходимо крайне осторожно. Люку необходимо добраться из точки A в точку B и доставить ценную и хрупкую посылку.
Для простоты будем считать, что местность разбита на квадраты и представляет из себя прямоугольник размером $n$ на $m$. Каждая клетка может быть одного из трех типов: здание, сугроб, либо лед. Перемещаться Люк может только между соседними клетками. Соседними считаются клетки, имеющие общую сторону. Перемещение между любыми двумя клетками занимает ровно одну единицу времени. Каждая клетка имеет свою высоту --- целое число.
Между соседними клетками зданий можно перемещаться без каких-либо ограничений. Также из здания можно переместиться в соседний сугроб. Из сугроба можно попасть в соседнее здание. Из сугроба можно перейти либо в соседний сугроб, либо на соседнюю клетку со льдом, если высота новой клетки не больше изначальной. Из клетки со льдом можно переходить в соседнюю клетку со льдом или сугробом, если высота новой клетки не больше изначальной. Если же Люк переходит из клетки со льдом в клетку со льдом, высота которой строго меньше, то он начинает скользить в том же направлении. Люк останавливает скольжение, если следующей клеткой на его пути встречается сугроб, клетка со льдом, высота которой больше высоты той клетки, в которой он находится, либо край карты. В этом случае Люк снова может идти в любом направлении из той клетки, в которой он остановился. Если же Люк встречает на своем пути стену здания, то он оказывается не в силах остановить движение и разбивает посылку.
Люку необходимо как можно скорее доставить это посылку из точки A в точку B. Помогите ему найти кратчайший путь, при котором его груз уцелеет.
В первой строчке входного файла заданы два числа $n$ и $m$ (1ドル \le n, m \le 500$) --- размеры карты. Во второй строке находятся два числа $a_r,ドル $a_c$ (1ドル \le a_r \le n, 1 \le a_c \le m$) --- номер строки и номер столбца, в которых находится точка A. В третьей строке находятся два числа $b_r,ドル $b_c$ --- описание точки B в том же формате. В каждой из следующих $n$ строчек находится $m$ символов. Если соответствующий символ равен $B,ドル то в этой клетке находится здание, $S$ --- сугроб и $I$ --- лед. В следующих $n$ строчках находится описание рельефа местности. В каждой из этих строчек --- по $n$ целых чисел --- высота соответствующей клетки на карте. Высота каждой точки --- целое число $h_{ij}$ (0ドル \le h_{ij} \le 10^9$).
Гарантируется, что точки A и B находятся в зданиях.
В выходной файл выведите длину кратчайшего пути из A в B, либо <<Impossible>>, если пути не существует.
3 5 1 1 3 5 BISSS SIIIS SSSIB 10 10 5 5 5 10 10 5 3 1 10 10 5 5 1
6