Minimum Cost Path in a Maze

You are given a maze in the form of an n x n grid. Each cell in the maze contains a non-negative integer representing the cost to enter that cell. Your task is to compute the minimum cost to travel from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1, n-1)). You can move in four directions: up, down, left, and right.

The cost of a path is defined as the sum of costs of all the cells visited, including the start and destination cells. Formally, if you traverse a path that goes through cells \( (i_0, j_0), (i_1, j_1), \ldots, (i_k, j_k) \), the total cost is:

[ \text{Total Cost} = \sum_{m=0}^{k} maze[i_m][j_m] ]

Your goal is to find the minimum possible cost.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n (\(1 \le n \le 1000\)) representing the number of rows and columns in the maze.
• The following n lines each contain n space-separated integers. The j-th integer in the i-th line represents the cost maze[i][j].

outputFormat

Output to stdout a single integer: the minimum cost required to travel from the top-left corner to the bottom-right corner of the maze.

3
1 2 2
4 5 6
7 8 1

12