AT_abc400_d [ABC400D] Takahashi the Wall Breaker

Takahashi is about to go buy eel at a fish shop. The town where he lives is divided into a grid of $ H $ rows and $ W $ columns. Each cell is either a road or a wall. Let us denote the cell at the $ i $ -th row from the top $ (1\leq i \leq H) $ and the $ j $ -th column from the left $ (1\leq j \leq W) $ as cell $ (i,j) $ . Information about each cell is given by $ H $ strings $ S_1,S_2,\ldots,S_H $ , each of length $ W $ . Specifically, if the $ j $ -th character of $ S_i $ $ (1\leq i \leq H,1\leq j\leq W) $ is `.`, cell $ (i,j) $ is a road; if it is `#`, cell $ (i,j) $ is a wall. He can repeatedly perform the following two types of actions in any order: - Move to an adjacent cell (up, down, left, or right) that is within the town and is a road. - Choose one of the four directions (up, down, left, or right) and perform a **front kick** in that direction. When he performs a front kick, for each of the cells at most $ 2 $ steps away in that direction from the cell he is currently in, if that cell is a wall, it becomes a road. If some of the cells at most $ 2 $ steps away are outside the town, a front kick can still be performed, but anything outside the town does not change. He starts in cell $ (A,B) $ , and he wants to move to the fish shop in cell $ (C,D) $ . It is guaranteed that both the cell where he starts and the cell with the fish shop are roads. Find the minimum **number of front kicks** he needs in order to reach the fish shop.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $ $ A $ $ B $ $ C $ $ D $

Print the minimum number of front kicks needed for Takahashi to reach the fish shop.

### Sample Explanation 1 Takahashi starts in cell $ (1,1) $ . By repeatedly moving to adjacent road cells, he can reach cell $ (7,4) $ . If he performs a front kick to the left from cell $ (7,4) $ , cells $ (7,3) $ and $ (7,2) $ turn from walls to roads. Then, by continuing to move through road cells (including those that have become roads), he can reach the fish shop in cell $ (7,1) $ . In this case, the number of front kicks performed is $ 1 $ , and it is impossible to reach the fish shop without performing any front kicks, so print $ 1 $ . ### Sample Explanation 2 Takahashi starts in cell $ (1,1) $ . When he performs a front kick to the right, cell $ (1,2) $ turns from a wall to a road. The cell two steps to the right of $ (1,1) $ is outside the town, so it does not change. Then, he can move to cell $ (1,2) $ and then to the fish shop in cell $ (2,2) $ . In this case, the number of front kicks performed is $ 1 $ , and it is impossible to reach the fish shop without performing any front kicks, so print $ 1 $ . ### Sample Explanation 3 When performing a front kick, it is fine if the fish shop’s cell is within the cells that could be turned into a road. Specifically, the fish shop’s cell is a road from the beginning, so it remains unchanged; particularly, the shop is not destroyed by the front kick. ### Constraints - $ 1\leq H\leq 1000 $ - $ 1\leq W\leq 1000 $ - Each $ S_i $ is a string of length $ W $ consisting of `.` and `#`. - $ 1\leq A,C\leq H $ - $ 1\leq B,D\leq W $ - $ (A,B)\neq (C,D) $ - $ H $ , $ W $ , $ A $ , $ B $ , $ C $ , and $ D $ are integers. - The cell where Takahashi starts and the cell with the fish shop are roads.