Given is an a x b matrix where every cell corresponds to either an empty space, denoted with a dot(.) or wall, denoted with X. This matrix represents a maze and in it there are also two creatures: creature One(1) and creature two(2). Creatures start at different empty spaces. And, somehow, they got synchronized: They do exactly the same movements when (1) goes west, so does (2); when (1) goes east, so does (2); and the same happens when they go south or north. They move at the same time: for example, if (1) is east of (2) and they move east, both creatures move. They cannot go to a location where there is an obstacle (or the other creature, unless it is moving away). For example, if there is an obstacle east of (1) but not (2), if they go east, they will stay in their current locations as (1) is blocked by the obstacle and (2) is blocked by (1). Creatures want to get out of this mysterious maze, and they want to do so at the very same time (that is, they want to leave the house with the same move) creatures get out of the maze if they move north in row 1, south in row a, west in column 1, or east in column b. This is proving to be very tricky. Please help them by designing an O((ab)^2) algorithm that computes the smallest number of moves for them to get out(or it will tell them that the task is impossible).