Shortest Path to Treasure

You are given an N x N grid representing a map. Each cell of the grid is either . (an empty space) or # (a wall). You are also given the starting coordinates \( (sx, sy) \) and the target (treasure) coordinates \( (tx, ty) \). Your task is to determine the minimum number of steps required to travel from the start to the treasure using only four directional movements: up, down, left, and right. If the destination is not reachable, output \(-1\).

Note: The problem can be solved using a breadth-first search (BFS) algorithm, which runs in \(O(N^2)\) in the worst-case scenario.

inputFormat

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

N
sx sy tx ty
row_1
row_2
...
row_N

Where:

• N is an integer representing the size of the grid.
• sx sy are the starting coordinates.
• tx ty are the target (treasure) coordinates.
• Each of the next N lines represents a row of the grid, which is a string consisting of the characters . and #.

outputFormat

Output the minimum number of steps required to reach the treasure from the start. If the treasure is unreachable, output -1. The output should be printed to standard output (stdout).

5
0 0 4 4
.....
.#.#.
.#...
.#..#
.....

8