A* Pathfinding in a 2D Grid

You are given a 2D grid representing a map. Each cell is either walkable (denoted by '.') or blocked (denoted by '#'). Your task is to find the shortest path from a given start position to a target position using the A* search algorithm.

The algorithm uses the Manhattan distance as a heuristic, which is defined as \( |r_1 - r_2| + |c_1 - c_2| \). If a valid path exists, output the number of steps in the path, followed by the coordinates of each step in order. Otherwise, output -1.

inputFormat

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

R C
row1
row2
...
rowR
start_row start_col
target_row target_col

Here, R and C are the number of rows and columns, respectively. Each of the next R lines is a string of length C representing a row of the grid. The last two lines provide the coordinates of the start cell and the target cell.

outputFormat

If a path exists, first print an integer N on the first line representing the number of cells in the path (including the start and target). Then print N lines, each containing two integers representing the row and column of each step along the path. If no valid path exists, print a single line with -1.

## sample

4 4
...#
.#..
...#
.#..
0 0
3 3

7
0 0
0 1
0 2
1 2
2 2
3 2
3 3

</p>