Robot Navigation with Turn Constraints

You are given a grid of size \( n \times m \) consisting of free cells (denoted by '.') and obstacles (denoted by 'X'). A robot is initially positioned at \( (s_x, s_y) \) and its target is at \( (t_x, t_y) \). The robot can move in 4 directions: right, down, left, and up. However, the robot is allowed to change its moving direction at most \( t \) times.

A turn is defined as a change in the direction of movement compared to the previous move. At the starting position, the robot has no previous direction, so the first move does not count as a turn.

Your task is to determine whether the robot can reach the target cell while making no more than \( t \) turns. If it is possible, output YES; otherwise, output NO.

Note: The grid indices are 0-based.

inputFormat

The input is read from stdin in the following format:

n m t
s_x s_y
 t_x t_y
row_1
row_2
... 
row_n

• The first line contains three integers: \( n \) (number of rows), \( m \) (number of columns), and \( t \) (the maximum allowed number of turns).
• The second line contains two integers: \( s_x \) and \( s_y \), representing the starting cell.
• The third line contains two integers: \( t_x \) and \( t_y \), representing the target cell.
• The next \( n \) lines describe the grid. Each line is a string of length \( m \) that consists of '.' (free cell) and 'X' (obstacle).

outputFormat

The output is a single line to stdout containing either YES if the robot can reach the target within \( t \) turns, or NO otherwise.

5 5 3
0 0
4 4
.....
.....
..X..
.....
.....

YES