Pathfinding Through Obstacles

You are given a grid of size \(N \times M\) representing an area, where each cell is either a free cell denoted by . or an obstacle denoted by any other character (in our problem, obstacles are represented by #). Your task is to determine whether there exists a valid path from the starting cell \((S_r, S_c)\) to the destination cell \((D_r, D_c)\). You can move only one step at a time in one of the four cardinal directions (up, down, left, and right). Moves that would take you outside the grid or into an obstacle are not allowed.

Note: The grid indices are 0-indexed. A valid move from cell \((x,y)\) is to \((x+dx, y+dy)\) where \((dx,dy)\) is one of \((-1,0)\), \((1,0)\), \((0,-1)\), or \((0,1)\) and the resulting cell satisfies \(0 \le x < N\) and \(0 \le y < M\), and contains a ..

Your program should read the input from stdin and write the output to stdout as described below.

inputFormat

The input is given in the following format:

N M
row1
row2
... 
rowN
S_r S_c D_r D_c

Where:

• \(N\) is the number of rows in the grid.
• \(M\) is the number of columns in the grid.
• Each of the next \(N\) lines represents a row of the grid; each row is a string of length \(M\) consisting of the character . (free cell) or # (obstacle).
• \(S_r\) and \(S_c\) are the starting row and column indices.
• \(D_r\) and \(D_c\) are the destination row and column indices.

outputFormat

Output a single line containing YES if a valid path exists from the starting cell to the destination cell, and NO otherwise.

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

YES