Rectangle Escape

Interview

Time limit2sMemory limit512 MB

Summary
A rectangle slides on a grid with walls; find the shortest sequence of unit moves taking its top-left cell from start to finish.
Level

Medium6 of 10

Topics
BFS, Prefix sum, Graph, Implementation
Solved
No attempts yet

Problem

A rectangle of size H×W is placed on a grid of size N×M. The grid is divided into cells of size 1×1. The top-left cell of the grid is (1, 1) and the bottom-right cell is (N, M). When the top-left cell of the rectangle is at (Sr, Sc), find the minimum number of moves needed to move the top-left cell of the rectangle to (Fr, Fc).

Each cell of the grid is either empty or a wall. The rectangle cannot be on a cell with a wall. Also, the rectangle cannot go outside the grid.

In one move, the rectangle can be moved one cell in one of the four directions: left, right, up, or down.

Input

The first line gives the size of the grid, N and M. From the second line, N lines give the information of each cell of the grid. 0 is an empty cell and 1 is a wall.

The last line gives the size of the rectangle H, W, the start coordinates Sr, Sc, and the destination coordinates Fr, Fc.

The coordinates of the grid are of the form (r, c), where r is the row and c is the column. They satisfy 1 ≤ r ≤ N and 1 ≤ c ≤ M.

Output

Print the minimum number of moves on the first line. If it is impossible to move, print -1.

Constraints

  • 2 ≤ N, M ≤ 1,000
  • 1 ≤ H ≤ N
  • 1 ≤ W ≤ M
  • 1 ≤ Sr ≤ N-H+1
  • 1 ≤ Sc ≤ M-W+1
  • 1 ≤ Fr ≤ N-H+1
  • 1 ≤ Fc ≤ M-W+1
  • The rectangle given in the input does not go outside the grid, and there is no wall in the cells where the rectangle is placed.

Examples2

  1. Example 1

    Input
    4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4
    Expected output
    7

  2. Example 2

    Input
    6 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
2 3 1 1 5 5
    Expected output
    8