Minimum Cost – Land Acquisition

Find the minimum cost for the government to acquire lands for road construction by selecting at most one building per row

Understand the Problem

Problem Statement

Minimum Cost – Land Acquisition: The government of India plans to build a road in a city. The government also plans to acquire some lands to start the construction. The program must accept an integer matrix of size N*N representing the heights of the buildings (i.e., the number of storeys in each building) in the city. A positive value X in the matrix indicates that there is an X-storey building. A zero value in the matrix indicates the presence of land that cannot be acquired by the government.

The rules for road construction in the city are given below:
– The road always starts from the first row and ends at the last row.
– No more than one building in a row can be acquired by the government.
The cost to acquire an X-storey building is X. The government has decided to acquire the lands with the minimum cost M. The program must print the minimum cost M to acquire land for road construction in the given city as the output.

NOTE: It is always possible to build a road in the given city.

Constraints

2 ≤ N ≤ 100
0 ≤ Matrix[i][j] ≤ 1000
At least one valid path from first row to last row exists
Zero values represent land that cannot be acquired
Positive values represent building heights (cost to acquire)

Examples

Example 1

Input

Output

Explanation

The minimum cost path is: 2 (row 0) → 1 (row 1) → 7 (row 2) → 1 (row 3) = 2 + 1 + 7 + 1 = 11

The path moves from the building of height 2 in the first row, to the building of height 1 in the second row (left diagonal), to the building of height 7 in the third row (right diagonal), and finally to the building of height 1 in the fourth row (left diagonal).

Example 2

Input

Output

Explanation

The minimum cost path is: 2 (row 0) → 1 (row 1) → 1 (row 2) = 2 + 1 + 1 = 4

The path moves from the building of height 2 in the first row, to the building of height 1 in the second row (right diagonal), and finally to the building of height 1 in the third row (right diagonal).

Solution

#include <stdio.h>
#include <limits.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int mat[n][n];
    
    // Read input matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &mat[i][j]);
        }
    }
    
    // Dynamic programming: update costs from second row onwards
    for (int r = 1; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (mat[r][c] == 0) {
                continue; // Skip unacquirable land
            }
            
            int minPrev = INT_MAX;
            int foundValid = 0;
            
            // Check three possible previous positions: left diagonal, top, right diagonal
            for (int k = -1; k <= 1; k++) {
                int prevCol = c + k;
                if (prevCol >= 0 && prevCol < n && mat[r-1][prevCol] != 0) {
                    if (mat[r-1][prevCol] < minPrev) {
                        minPrev = mat[r-1][prevCol];
                    }
                    foundValid = 1;
                }
            }
            
            // Update current cell with minimum cost path
            if (foundValid) {
                mat[r][c] += minPrev;
            } else {
                mat[r][c] = 0; // No valid path to this cell
            }
        }
    }
    
    // Find minimum cost in the last row
    int minCost = INT_MAX;
    for (int j = 0; j < n; j++) {
        if (mat[n-1][j] != 0 && mat[n-1][j] < minCost) {
            minCost = mat[n-1][j];
        }
    }
    
    printf("%d\n", minCost);
    return 0;
}

Time:O(N²)

Space:O(N²)

Approach:

C Solution Explanation:

Input Reading: Read the matrix dimensions and populate the 2D array
Dynamic Programming Loop: For each row starting from the second row, examine each cell
Transition Logic: For each acquirable building (non-zero), check the three possible previous positions (left diagonal, directly above, right diagonal)
Cost Update: Add the minimum cost from valid previous positions to the current building's cost
Invalid Paths: If no valid previous path exists, mark current cell as unacquirable (set to 0)
Result Extraction: Find the minimum non-zero value in the last row, which represents the minimum cost path

The solution uses a bottom-up dynamic programming approach where each cell stores the minimum cost to reach that position from the first row.

Visual Explanation

Loading diagram...

All Problems