We are given a $M \times N$ grid where each tile is either a land or water tile. We may move from a land tile to any other land tile that is orthogonally adjacent to the current land tile. We may move from a water tile to any adjacent water tile (both orthogonally or diagonally will work for water tiles). We may not move from land to water or water to land.
It seems intuitive that if there exists a land-based path from the top row to the bottom row of the grid, then there cannot exist a water-based path from the left-most column to the right-most column. Conversely, if there is no water-based path from the left-most column to the right-most column, then there is a land-based path from the top row to the bottom row.
How might one go about proving the above claim? I am not sure what techniques are appropriate for this type of problem.
Originally, I had thought that the water movement needed to be only orthogonally adjacent for the above result to hold, but I found a counterexample.
EDIT: Orthogonally adjacent points of $(m,n)$ are $(m,n+1),(m,n-1),(m+1,n),(m-1,n)$. Diagonally adjacent points of $(m,n)$ are $(m+1,n+1),(m-1,n-1),(m+1,n-1),(m-1,n+1)$.