Grid Coloring with Yellow and Blue

ID: 13799

Type: Default

1000ms

256MiB

We are given a grid of size $N \times M$ consisting of cells. Some cells are obstacles (denoted by #) and cannot be passed, while other cells are walkable (denoted by .). We need to color the walkable cells following these rules:

Start at any walkable cell in the grid. This starting cell becomes the current cell.
From the current cell, choose a direction (up, down, left, or right), and move continuously in that direction until you either reach the boundary of the grid or encounter an obstacle. Note that you cannot stop in between.
If the movement is horizontal (left or right), then every cell you pass through (including the starting cell) is painted yellow. If the movement is vertical (up or down), then every cell you pass through (including the starting cell) is painted blue. (If there is an obstacle immediately in the chosen direction and you cannot move, the starting cell still gets painted.)
If all walkable cells have been painted at least once in yellow and at least once in blue, the coloring is considered successful and the process stops.
Otherwise, take the cell where you stopped (i.e. the last cell reached by your move) as the new current cell and repeat steps 2–4. If no matter how the moves are chosen, it is impossible to ensure that every walkable cell gets painted at least once in both yellow and blue, the process fails.

For example, consider a $2 \times 3$ grid where all cells are walkable. If you start at cell $(0,0)$ , regardless of the sequence of moves, it is impossible to paint every walkable cell at least once in both colors. However, if you start from cell $(0,1)$ , a valid sequence of moves exists that paints every cell with both colors.

Your task is to implement the function

$$int \; yellowblue(int\; N,\; int\; M,\; vector\; V); $$

where:

$N$ and $M$ represent the number of rows and columns respectively.
$V$ is an array of $N$ strings, each of length $M$ . In the string $V[i]$ , the $j$ -th character is . if the cell $(i, j)$ is walkable and # if it is an obstacle.

The function should return 1 if there exists a sequence of moves (starting from some walkable cell) that results in every walkable cell being painted at least once in yellow and at least once in blue, and return 0 otherwise.

Note:

The function ( yellowblue ) will only be called once.
Your submitted code should implement the function as described without performing any input/output operations or accessing any files.

inputFormat

The function receives the following parameters:

An integer $N$ representing the number of rows.
An integer $M$ representing the number of columns.
A vector of strings $V$ of length $N$ , where each string has $M$ characters. A character . denotes a walkable cell and # denotes an obstacle.

There is no additional input.

outputFormat

The function should return an integer. It returns 1 if it is possible to paint every walkable cell at least once in both yellow and blue following the given rules, and 0 otherwise.

sample

2 3
...
...

#P11708. Grid Coloring with Yellow and Blue

Grid Coloring with Yellow and Blue