Longest Path in a Maze

You are given an n × m maze represented as a grid. Each cell in the grid is either 1 (accessible) or 0 (blocked). Your task is to find the longest simple path from the top-left cell (position (0,0)) to the bottom-right cell (position (n-1, m-1)). A simple path is one in which no cell is visited more than once.

You may only move in the four cardinal directions: up, down, left, and right. The path length is defined as the number of cells visited, including the start and end cells. If either the start or the destination cell is blocked, or if no valid path exists, output -1.

The problem can be formally described using the following conditions:

• Let \(grid\) be a matrix where \(grid[i][j] \in \{0,1\}\).
• You start at cell \((0,0)\) and must reach cell \((n-1, m-1)\).
• You can move horizontally or vertically to an adjacent cell if that cell contains a 1 and has not been visited before.
• If a valid path exists, compute its length. Otherwise, return \( -1 \).

Solve this problem using an appropriate search technique such as DFS with backtracking.

inputFormat

The first line contains two integers, (n) and (m), representing the number of rows and columns in the grid, respectively. This is followed by (n) lines, each containing (m) space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer representing the length of the longest simple path from the top-left to the bottom-right cell. If no valid path exists, print -1.## sample

4 4
1 1 0 1
0 1 1 0
1 0 1 1
1 1 1 1

7