Path Existence in a Grid

You are given a grid with N rows and M columns. Each cell in the grid is either open (O) or blocked (X). Your task is to determine whether there is a path from the top-left cell (position (1,1)) to the bottom-right cell (position (N,M)).

A valid move is to move one cell at a time in one of the four cardinal directions (up, down, left, right). You cannot move outside the grid or move into a blocked cell.

Formally, let \(G_{ij}\) denote the cell in the \(i^{th}\) row and \(j^{th}\) column. A path is a sequence of cells \(\{(i_1,j_1), (i_2,j_2), \ldots, (i_k,j_k)\}\) where \((i_1,j_1) = (1,1)\) and \((i_k,j_k) = (N,M)\) such that for every \(t\) (\(1 \leq t < k\)), the adjacent cell \((i_{t+1},j_{t+1})\) is directly up, down, left, or right from \((i_t,j_t)\) and all visited \(G_{ij} = O\).

Output YES if such a path exists and NO otherwise.

inputFormat

The first line contains two integers, N and M (the number of rows and columns respectively). Following this, there are N lines, each containing a string of length M representing a row of the grid. Each character is either O (open cell) or X (blocked cell).

outputFormat

Output a single line containing YES if there exists a path from the top-left to the bottom-right cell, or NO otherwise.

3 3
OXO
OOX
XOO

YES