Problem Statement

Rook Movement Problem Description In chess, a rook is a piece that travels in a straight line, horizontally or vertically, through any number of empty squares. Formally, in a single move the rook can head in any one of [UP, DOWN, LEFT, RIGHT] , sliding across as many unoccupied squares as it likes in that direction. Given the rook's starting square (A, B), its target square (C, D), and a layout of the board, work out the fewest moves needed to bring the rook to the target, or report that it cannot be done, assuming every other piece on the board stays where it is. Unlike a standard chessboard, here the board measures N x M. Its layout is given as a 2D array of "0"/"1" strings, where 0 marks an empty square and 1 marks an occupied one. NOTE: The starting square and the target square are guaranteed to be empty. Rows are numbered from top to bottom and columns are numbered from left to right. Problem Constraints 1 <= N, M <= 1000 1 <= A, C <= N 1 <= B, D <= M Input Forma