#C3081. Drone Navigation in a City Grid
Drone Navigation in a City Grid
Drone Navigation in a City Grid
You are given a grid representing a city, where each cell is either free (represented by '.') or blocked by obstacles (represented by '#'). A drone starts at position \( (s_x, s_y) \) and needs to reach a destination at position \( (d_x, d_y) \). The drone can move up, down, left, or right. Your task is to determine if the drone can reach the destination without passing through obstacles.
The grid is of size \( n \times m \). The starting and destination positions are provided using 1-indexed coordinates. Formally, if we denote the grid as \( G \), where \( G_{i,j} \) is the cell at row \( i \) and column \( j \), then the drone can only move from \( (i, j) \) to \( (i-1, j) \), \( (i+1, j) \), \( (i, j-1) \), or \( (i, j+1) \) if the destination cell is within bounds and \( G_{i,j} = '.' \).
Conditions to note:
- If either the starting cell or the destination cell is blocked (i.e. \( '#' \)), then the answer is NO.
- The movement is only allowed to adjacent cells (no diagonal moves). </p>
inputFormat
The input is read from standard input (stdin) and is formatted as follows:
n m grid_row_1 grid_row_2 ... grid_row_n s_x s_y d_x d_y
Where:
- \( n \) and \( m \) are integers representing the number of rows and columns in the grid respectively.
- Each of the next \( n \) lines contains a string of length \( m \) consisting of characters '.' and '#'.
- \( s_x, s_y \) are the 1-indexed starting row and column indices and \( d_x, d_y \) are the 1-indexed destination row and column indices.
outputFormat
Output a single line to standard output (stdout) containing either YES
if the drone can reach the destination from the starting position without passing through obstacles, or NO
if it cannot.
5 5
.....
.#...
....#
.#.#.
...#.
1 1 5 5
YES
</p>