Statement

James wants to play his new videogame Dangerous Parkour (DP). But after booting up the game, he realized that the game is incomplete. In fact, the developer forgot to add the levels to the game, and the character is only allowed to move right! A level in DP is an N × M grid of cells, where cell (0, 0) is the top-left cell and cell (N-1, M-1) is the bottom-right cell. Each cell is either empty (`.') or contains a wall (`#'). James starts at cell (0, 0) and must reach cell (N-1, M-1) by making some (possibly 0) moves to the right: at any point, if James is at cell (i, j) and cell (i, j+1) is empty, he can move to cell (i, j+1). He may then start to fall down to cell (i+1, j+1), (i+2, j+1), (i+3, j+1), and so on, until he either stands on top of a wall or reaches the bottom of the grid. James is not allowed to make a right move while falling down. The fall damage is very high, and James can survive a fall of at most 1 cell...