408721: GYM103270 K Rat Maze

Katya loves rats, and she has many such pets that she takes care of. Rats are very social and intelligent creatures—not to mention they have beady eyes and stringy tails and the cutest little paws...

Katya has recently been training her rats to follow different scents and use scent trails to solve mazes. To train a rat, Katya will design a maze layout and then build it in her room using cardboard boxes for the barriers. Then she will mark a path from a start location to an exit location in the maze with a scent trail, using the specific scent that the rat was trained to recognize.

Now that Katya's rats have gotten pretty good at this task, she wants to run several of her rats through a maze at the same time, to see how their speeds compare and whether they will be distracted by the presence of other rats. However, she wants it to be easy enough for a particular rat to recognize its custom scent trail, so she will avoid marking any one section of the maze with more than one scent.

Help Katya mark paths for her rats in a maze that she designed! Given a grid map of the maze with # denoting a barrier, . denoting an open cell that can be traversed, and S and E denoting the starting and ending cells respectively, output the maximum number of paths from S to E which never overlap.

The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 500$$$), denoting the number of rows and columns in the grid to follow. The next $$$N$$$ lines each contain $$$M$$$ characters, representing cells in the rat maze.

Then the next line contains two integers $$$S_r$$$ and $$$S_c$$$, denoting the zero-indexed row and column indices respectively where the start cell is located, and likewise, the following line contains $$$E_r$$$ and $$$E_c$$$ with the location of the end cell.

Output the maximum number of paths from the start cell to the end cell that can be marked simultaneously in the maze as scent trails.

Note that for a rat be able to follow a scent from one cell to another, the two cells must be adjacent in that one is immediately above, below, to the left, or to the right of the other cell.

15 9
.#.......
.........
..E...#..
.#..#....
#..#.....
##.#..###
.........
.#.#...#.
..#......
.........
...#.....
S..#...#.
....#.#..
#........
.....##.#
11 0
2 2

2

7 14
..............
#...#.....#.#.
..#...#.......
........#.....
.#..S.......E.
...#.....#...#
......#.##.#..
4 4
4 12

3