C. Doppelganger

No Submission Yet

Problem Statement

It is time for LHS's annual prep rally! To encourage cooperation, the Principal decides to organize a fun team exercise. Feeling the teamwork spirit, Alicia and Kevin volunteer to participate together. The exercise can be visualized as \(2\) maps of size \(N\) by \(M\). Alicia initially starts in map 1 at \((x_1,y_1)\), and Kevin starts in map 2 at \((x_2,y_2)\). During each move, they can choose to move up, down, left, or right. However, when they choose a move, both Alicia and Kevin will have to attempt to move in the same direction, i.e. if they choose to move up, both will simultaneously try to move up. Their goal is to use the minimum number of moves for Alicia to be at \((ex_1,ey_1)\), and Kevin to be at \((ex_2,ey_2)\). However, of course, the exercise is not so simple, and there are many obstacles in the way. If a cell is blocked then they can’t move into it. Furthermore, for a move, if one person can perform it without bumping into the border or obstacle, but the other can not, then the person who can will move while the other person will stay in the same place.

As their friend, you want to help them ace this exercise as quickly as possible. Determine if its impossible, or find the minimum number of moves needed to finish this task.

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 128mb


\(1 \leq x_1, x_2, ex_1, ex_2 \leq N \leq 50\)
\(1 \leq y_1, y_2, ey_1, ey_2 \leq M \leq 50\)
It is further guarenteed that the starting and ending locations won't be blocked.

Input format

The first line contains \(2\) numbers \(N\), \(M\).
The second line contains \(4\) numbers \(x_1\), \(y_1\), \(x_2\), \(y_2\).
The third line contains \(4\) numbers \(ex_1\), \(ey_1\), \(ex_2\), \(ey_2\).
The next \(N\) lines each contain a string of length \(M\), which describes the first map. If the \(i\)th row and \(j\)th column is '#', then there is a obstacle, and is unblocked if it is '.'
The last \(N\) lines each contain a string of length \(M\), which describes the second map using the same format.

Output format

Output \(-1\) if the task is impossible. Otherwise, output a single integer indicating the minimum number of moves.

Sample input:

4 3
4 1 2 3
2 1 1 1

Sample output


Sample Explanation

A valid sequence of moves for both of them to reach their targets is Left, Left, Up, Up.

Contact Us
LIT Discord Server