408719: GYM103270 I Walk in the Park

Two dog walkers, Aarvind and Bailey, are planning a Saturday afternoon walk at the local dog park! The dogs they are walking love specific areas in the park (i.e. places with special sticks or other dogs), and Aarvind and Bailey have taken the time to mark these spots on a map of the dog park. Specifically, Aarvind's dogs like the two spots marked with a, and Bailey's dogs like the two spots marked with b.

Aarvind and Bailey want to plot out paths for their respective walks, traveling from one of their dogs' favorite spots to the other before ending the walk. However, they don't want to do too much walking. They would also like to meet up somewhere in the middle of their walks to let all of the dogs play together! Given a map of the park, help Aarvind and Bailey plot two paths of minimum combined length that intersect in at least one spot in the park.

The first line of input contains two integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 500$$$), which give the number of rows and columns in the dog park map respectively.

$$$N$$$ lines follow, each containing $$$M$$$ characters denoting grid cells on the park map. A # character denotes a tree in the park that cannot be walked through. A . denotes a patch of grass that can readily be traversed. Then an a denotes a start or end location for Aarvind, and a b character denotes a start or end location for Bailey.

Note that at each step of their walks, Aarvind and Bailey can only move into an adjacent cell, where an adjacent cell is defined to be one either above, below, to the left, or to the right of the current cell on the map. Additionally, Aarvind and Bailey can always walk through map cells marked with a or b.

Following the $$$N$$$ lines containing the park map are four lines of input. The first two of these lines each contain two integers $$$a_r$$$ and $$$a_c$$$, giving the row and column location of an a character marked on the map. Likewise, the next two lines each contain $$$b_r$$$ and $$$b_c$$$ with the location a b character.

Print the minimum possible sum of the lengths of two paths—one for Aarvind connecting the a cells and another for Bailey connecting the b cells—such that the two paths intersect at at least one location in the park. If no such paths are possible, simply print the string IMPOSSIBLE.

12 9
...#...#.
#.####.##
#b..####.
..###....
.....#..#
..#...###
.....#.##
.......a.
......#.#
.#b.#....
##.a.#.#.
.#....#..
7 7
10 3
2 1
9 2

17

6 8
.a.....#
....#.##
.....#.b
..###...
a..#b...
..#..###
0 1
4 0
2 7
4 4

IMPOSSIBLE

For the first sample case, the following paths result in the minimal sum of 17, where cells that are a part of the solution paths are marked with * and the intersection cell is marked with X:

...#...#.

#.####.##

#b..####.

.*###....

.*...#..#

.*#...###

.**..#.##

..X****a.

..**..#.#

.#b*#....

##.a.#.#.

.#....#..