Roll the Bar

All submissions for this problem are available.
###Read problems statements [Mandarin](http://www.codechef.com/download/translated/LTIME69/mandarin/ROLLBAR.pdf) , [Bengali](http://www.codechef.com/download/translated/LTIME69/bengali/ROLLBAR.pdf) , [Hindi](http://www.codechef.com/download/translated/LTIME69/hindi/ROLLBAR.pdf) , [Russian](http://www.codechef.com/download/translated/LTIME69/russian/ROLLBAR.pdf) and [Vietnamese](http://www.codechef.com/download/translated/LTIME69/vietnamese/ROLLBAR.pdf) as well. You are given a $1 \times 1 \times 2$ bar (a cuboid) and a grid $A$ with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Let's denote the cell in row $r$ and column $c$ by $(r, c)$. Some cells of the grid are blocked, the remaining cells are free. Each cell has dimensions $1 \times 1$, the same as two opposite faces of the cuboid. When the bar is placed on the grid in such a way that one of its two $1 \times 1$ faces fully covers a cell $(r, c)$, we say that the bar is *standing on* the cell $(r, c)$. Initially, the bar is standing on a cell $(x, y)$. When the bar is placed on the grid, one of its faces is touching the grid; this face is called the *base*. In one move, you must roll the bar over one of its base edges (sides of the base); this base edge does not move and the bar is rotated $90^\circ$ around it in such a way that it is still lying on the grid, but with a different base. In different moves, the bar may be rotated around different edges in different directions. After each move, the base of the bar must lie fully inside the grid and it must not cover any blocked cells. An example sequence of moves is shown [here](http://freegifmaker.me/img/res/1/5/5/0/6/9/15506903141352867.gif). For each cell of the grid, determine the minimum number of moves necessary to achieve the state where the bar is standing on this cell or determine that it is impossible to achieve. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $M$.  The second line contains two spaceseparated integers $x$ and $y$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains $M$ integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}$ (a string with length $M$). For each valid $i, j$, $A_{i, j} = 0$ denotes that the cell $(i, j)$ is blocked and $A_{i, j} = 1$ denotes that it is free. ### Output For each test case, print $N$ lines, each containing $M$ spaceseparated integers. For each valid $i, j$, the $j$th integer on the $i$th of these lines should denote the minimum number of moves necessary to have the bar stand on cell $(i, j)$, or it should be $1$ if it is impossible. ### Constraints  $1 \le T \le 50$  $1 \le N, M \le 1,000$  $1 \le x \le N$  $1 \le y \le M$  $0 \le A_{i, j} \le 1$ for each valid $i, j$  $A_{x, y} = 1$  the sum of $N \cdot M$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (15 points):**  $x = 1$  $y = 1$  $A_{i, j} = 1$ for each valid $i, j$ **Subtask #2 (85 points):** original constraints ### Example Input ``` 2 2 4 1 1 1111 0111 2 4 1 1 1111 0011 ``` ### Example Output ``` 0 1 1 2 1 1 1 3 0 1 1 2 1 1 1 1 ``` ### Explanation **Example case 1:** Initially, the base of the bar occupies the cell $(1, 1)$. After the first move, it occupies the cells $(1, 2)$ and $(1, 3)$. After the second move, it can occupy the cell $(1, 4)$. Alternatively, after the second move, it can occupy the cells $(2, 2)$ and $(2, 3)$, and after the third move, it can occupy the cell $(2, 4)$.Author:  deva2802 
Editorial  https://discuss.codechef.com/problems/ROLLBAR 
Tags  bfs, deva2802, easymedium, graphtheory, ltime69 
Date Added:  21022019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions