Minimum Moves on a Restricted Grid

You are given a grid of characters, where each cell is either '0' or '1'. You start from a given cell and want to reach a target cell. However, you can only traverse cells that have the same type as the starting cell. From any cell, you can move in the four cardinal directions (up, down, left, right). Your task is to compute the minimum number of moves required to reach the target cell. If the target cell cannot be reached, output -1.

Formally, let the grid be a matrix \(G\) of size \(N \times M\) with indices starting at 0. You are given starting coordinates \((s_x, s_y)\) and target coordinates \((t_x, t_y)\). You may move from \((x, y)\) to \((x+1, y)\), \((x-1, y)\), \((x, y+1)\), or \((x, y-1)\) if and only if the new cell has the same character as \(G[s_x][s_y]\) and lies within the grid bounds.

The problem can be solved using a breadth-first search (BFS) algorithm which guarantees finding the shortest path (if one exists).

inputFormat

The input is read from standard input and has the following format:

N M
row1
row2
... 
rowN
s_x s_y t_x t_y

Here:

• The first line contains two integers \(N\) and \(M\) representing the number of rows and columns of the grid.
• Each of the next \(N\) lines contains a string of length \(M\) representing a row of the grid.
• The last line contains four integers: \(s_x\), \(s_y\), \(t_x\), and \(t_y\), representing the starting and target cell coordinates respectively.

outputFormat

Output a single integer representing the minimum number of moves required to reach the target cell from the starting cell. If it is not possible to reach the target cell, print -1.

4 4
0000
0110
0110
0000
0 0 3 3

6