405921: GYM102157 2 Does it Percolate?

Percolation is the process of a liquid slowly passing through a filter or surface. We will consider a 2d mesh or lattice grid for our surface.

A lattice grid here is a normal 2-dimensional grid (where each cell is connected to at most 4 cell at its 4-side) with an additional circular connection at its border. Meaning if we have a lattice of dimension (4, 5) then cell at position (2, 1) will have a connection with cell (2, 5), and cell at position (1, 4) will have a connection with cell (4, 4). In other words the left-most cells will have a connection with the right-most cells in the same row and the top-most cells will have a connection with the bottom-most cells in the same column.

Each lattice grid is made of different surface or material, which determines the atomic gap in each cell and whether it will allow any liquid to pass through. For each cell (i, j) in the lattice you will be given the probability p_ij of accepting any given liquid. Each liquid also has its own probability threshold p, if any cell has less probability than p then that liquid does not pass through and that cell remains unoccupied.

Given the details of lattice cells and the threshold p it will create clusters of occupied cells (by the liquid) using the connection of each cell. Now if at least one of the cluster has all the following characteristics then the lattice percolates—

* Has at least 1 cell from each row.

* Has at least 1 cell from each column.

The first line of input contains two integers and a float. The two integers n and m (1 ≤ n, m ≤ 1000) indicates width and length of the lattice. The float p (0.00 ≤ p ≤ 1.00) indicates the threshold for the given liquid.

The following n lines each contains m floats p₁₁, p_ij, ...p_nm which indicates the probability of accepting any given liquid for cell (i, j).

The input data set is big.

Print 'YES' if the lattice percolates or else 'NO', without the qoutes.

4 4 0.50
0.19 0.52 0.23 0.33
0.78 0.65 0.45 0.49
0.48 0.66 0.77 0.89
0.30 0.36 0.88 0.15

YES

3 3 0.10
0.09 0.09 0.09
0.09 0.10 0.09
0.09 0.09 0.09

NO