410663: GYM104072 A Arrow Matrix

Two pawns found themselves stuck in an $$$N$$$ by $$$M$$$ matrix consisting of arrows (up, right, down, left), where no arrow points to the outside of the matrix. The only way they can escape is if they manage to meet in a matrix cell at the same time.

Each second, both pawns will make one move in the direction shown by the arrow from their current cell.

Your job is to make exactly one change to an arrow by orientating it to another direction than the initial one (no arrow should point to the outside of the matrix). A change is valid, if when the pawns start moving from their initial positions, they will meet in the same matrix cell at some point in time.

You need to calculate the number of different valid changes. Two changes are different, if the resulting matrices are different from each other.

The first line of the input contains the integers $$$N$$$ and $$$M$$$ ($$$1 \leq N*M \leq 10^6$$$), denoting the number of lines and columns of the matrix.

The second line contains two integers $$$X_1$$$ and $$$Y_1$$$ ($$$1 \leq X_1 \leq N$$$, $$$1 \leq Y_1 \leq M$$$), denoting the initial position of the first pawn.

The third line contains two integers $$$X_2$$$ and $$$Y_2$$$ ($$$1 \leq X_2 \leq N$$$, $$$1 \leq Y_2 \leq M$$$), denoting the initial position of the second pawn.

Each of the following $$$N$$$ lines contains a string of $$$M$$$ characters, describing the configuration of the arrows of that line. Thus, the $$$j$$$-th character of the $$$i$$$-th line ($$$1 \leq i \leq N$$$, $$$1 \leq j \leq M$$$) describes the orientation of the arrow from the line $$$i$$$ and column $$$j$$$ in the matrix:

• $$$0$$$ - the arrow is pointing up
• $$$1$$$ - the arrow is pointing right
• $$$2$$$ - the arrow is pointing down
• $$$3$$$ - the arrow is pointing left

It is guaranteed that no arrow points to the outside of the matrix.

Output the total number of different valid changes.

2 3
1 2
2 1
222
113

7

5 3
2 1
1 2
222
222
222
222
113

22

The initial matrix of the first example is:

$$$$$$ \begin{matrix} \downarrow & \downarrow & \downarrow\\ \rightarrow & \rightarrow & \leftarrow \end{matrix} $$$$$$