Problem Statement

There is a rectangular board with R rectangular obstacles placed on it. The board consists of N×M square cells; the bottom-left corner of the board is the cell with coordinates (0, 0), and the top-right cell has coordinates (N-1, M-1). Each obstacle is described by the coordinates of its bottom-left and top-right corners. In other words, the obstacle described by coordinates (X1, Y1)-(X2, Y2) blocks all cells with coordinates (x, y), such that X1 ≤ x ≤ X2 and Y1 ≤ y ≤ Y2. For example, two obstacles described by (2, 0)-(2, 2) and (1, 1)-(3, 1) will block five cells: Note that the obstacles may intersect with each other. What is the length of the shortest path between the bottom-left and the top-right corner? You can move from a cell to any other cell with which it shares a side (i.e. you can move one step up, down, left or right), as long as the destination is not blocked by an obstacle and is not outside the bounds of the board. Write a function: def solution(N, M, X1