#C3081. Drone Navigation in a City Grid

    ID: 46469 Type: Default 1000ms 256MiB

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.

    ## sample
    5 5
    .....
    .#...
    ....#
    .#.#.
    ...#.
    1 1 5 5
    
    YES
    

    </p>