Treasure Hunt in a Dynamic Maze

In this problem, you are given a maze described by a matrix with r rows and c columns. The maze contains passable cells denoted by . and impassable cells denoted by #. In addition, there are k triggers. The i-th trigger behaves as follows: whenever Xiao Ming steps on the cell at position \( (r_i, c_i) \) (1-indexed), the cell at position \( (R_i, C_i) \) will toggle its state; that is, if it was passable (denoted by \( . \)), it becomes impassable (denoted by \( # \)) and vice versa. The start and treasure positions are guaranteed to be passable at the beginning, and no trigger is located at these positions.

Xiao Ming is initially located at a given starting cell, and a treasure is hidden in another cell. He can only move within the boundaries of the maze using steps in the four cardinal directions (up, down, left, right) and cannot step into an impassable cell. Determine the minimum number of steps that Xiao Ming must take to reach the treasure. If the treasure cannot be reached, output -1.

The maze, the starting and treasure positions, and the triggers are provided as input. Note that if Xiao Ming steps on a trigger cell, the specified other cell will toggle its state immediately (affecting subsequent moves).

Note on formulas: All formulas must be rendered in LaTeX. For example, the maze dimensions are given as \( r \) rows and \( c \) columns, and a trigger at \( (r_i, c_i) \) toggles the cell at \( (R_i, C_i) \).

inputFormat

The first line contains three integers \( r \), \( c \), and \( k \) indicating the number of rows, columns, and triggers respectively.

The following \( r \) lines each contain a string of length \( c \) representing the maze. Each character is either . (passable) or # (impassable).

The next two lines each contain two integers. The first of these lines gives the starting cell coordinates \( (s_x, s_y) \) and the second gives the treasure cell coordinates \( (t_x, t_y) \) (both 1-indexed).

Then, \( k \) lines follow. Each line contains four integers: \( r_i \), \( c_i \), \( R_i \), and \( C_i \). This means that when Xiao Ming steps on the cell at \( (r_i, c_i) \), the state of the cell at \( (R_i, C_i) \) is toggled.

outputFormat

Output a single integer representing the minimum number of steps needed to reach the treasure. If the treasure cannot be reached, output -1.

sample

3 3 1
...
.#.
...
1 1
3 3
1 2 2 2

4