You are given a matrix \(n*m \). The matrix rows are numbered from \(1 \) to \(n\) from top to bottom and the matrix columns are numbered from \(1\) to \(m\) from left to right. The cells of the field at the intersection of the \(x^{th}\) row and the \(y^{th}\)column has coordinates \((x, y)\).
Every cell is empty or blocked. For every cell \((x, y)\), determine if you change the state of cell \((x, y)\)(empty to blocked or blocked to empty), then is it possible to reach cell \((n, m) \) from \((1, 1) \) by going only down and right.
Input format
- The first line contains two space-separated numbers \(n, m \) denoting the number of rows and columns.
- Next \(n\) lines contain symbols. If the symbol on \((x, y)\) is '#', then the cell is blocked. Otherwise, if the symbol is '.', then the cell is empty.
Output format
Print \(n\) lines where every line contains \(m\) numbers. Print 0 if it is impossible to reach \((n, m) \). Otherwise, print 1.
Constraints
\(1 \le n, m \le 10^3 \)
5 5 ..#.. #...# #...# ....# .##..
0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0
If we blocked cell \((1, 1) \) or \((5, 5) \), it is obvious that the answer won't exist.
If we blocked cell \((1, 2) \) or \((2, 2) \), from the left-top corner, we cant achieve cell \((5, 5) \), since all paths are blocked off.
If we blocked cell \((5, 4) \) or \((4, 5) \), all possible passes from \((5, 5) \) are blocked off.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor