Interview Question

Can someone help me to solve this task? The prisoner is trying to escape from the castle, which consists of MN square rooms arranged in an M\xD7N rectangle. Between any two...

Can someone help me to solve this task?
The prisoner is trying to escape from the castle, which consists of M*N square rooms arranged in an M\xD7N rectangle. Between any two adjacent rooms there is a door, but some rooms are closed and cannot be entered. Initially, the prisoner is in the corner room and to save him, he needs to get into the opposite corner room. He doesn\'t have much time, so he needs to take the shortest route. You are required to find the shortest route leading to salvation.

Input data: An array M * N containing characters (0 or 1). If the character is 1, then the room can be entered, if it is 0, then the room is closed. The prisoner\u2019s initial position is the lower left corner( the first character of the last line), the exit is in the upper right corner( the last character of the first line, both of these characters are equal to 1).

Output: The program should print the number of routes leading the prisoner to the exit and passing through M + N -1 room or the word < impossible> if no such routes exist.