Tree Shadow within Matrix

Count trees whose shadows fall within a rectangular matrix field based on sunlight direction

Understand the Problem

Problem Statement

Certain number of trees are planted in a rectangular matrix field. The trees were planted in an R*C rectangular matrix but certain trees did not grow due to lack of ground water. Hence the cells in the matrix which have the trees are indicated by 1 and the cells which do not have trees in it are indicated by 0.

The shadow of the trees always falls on the adjacent cell depending on the direction of the sunlight (The direction of the sunlight can be left-L, right-R, front-F and back-B of the rectangular field). The shadow of a tree does not fall on the ground within the rectangular field if the adjacent cell has a tree. The program must print the count of trees whose shadow falls within the rectangular field (The trees whose shadow falls outside the rectangular matrix field must not be counted. This happens when the trees are along the border and their shadow is outside the rectangular matrix field).

Constraints

The number of rows R must be between 2 and 50 (inclusive)
The number of columns C must be between 2 and 50 (inclusive)
Each cell in the matrix contains either 1 (tree present) or 0 (no tree)
The direction parameter must be exactly one of: L (left), R (right), F (front), B (back)
The matrix dimensions R and C are provided as space-separated integers on the first line
The direction is provided as a single uppercase character on the last line

Examples

Example 1

Input

Output

Explanation

With sunlight from the left, shadows fall to the right. The trees at positions (0,0), (0,3), (1,1), and (2,2) have empty cells to their right, so their shadows fall on the ground within the matrix. Trees at (1,3), (1,4) have other trees to their right, so their shadows don't count.

Example 2

Input

Output

Explanation

With sunlight from the back, shadows fall forward (downward). The trees at positions (0,0), (1,3), and (1,4) have empty cells below them, so their shadows fall on the ground within the matrix. Other trees either have trees below them or are at the bottom edge.

Example 3

Input

Output

Explanation

With sunlight from the right, shadows fall to the left. The trees at positions (0,1) and (1,2) have empty cells to their left, so their shadows fall on the ground within the matrix.

Solution

#include <stdio.h>

int main() {
    int R, C;
    scanf("%d %d", &R, &C);
    
    int matrix[50][50];
    
    // Read the matrix
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    
    char direction;
    scanf(" %c", &direction);
    
    int count = 0;
    
    if (direction == 'L') {
        // Sun from left, shadow to right
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C - 1; j++) {
                if (matrix[i][j] == 1 && matrix[i][j + 1] == 0) {
                    count++;
                }
            }
        }
    } else if (direction == 'R') {
        // Sun from right, shadow to left
        for (int i = 0; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (matrix[i][j] == 1 && matrix[i][j - 1] == 0) {
                    count++;
                }
            }
        }
    } else if (direction == 'B') {
        // Sun from back, shadow forward (down)
        for (int i = 0; i < R - 1; i++) {
            for (int j = 0; j < C; j++) {
                if (matrix[i][j] == 1 && matrix[i + 1][j] == 0) {
                    count++;
                }
            }
        }
    } else if (direction == 'F') {
        // Sun from front, shadow backward (up)
        for (int i = 1; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (matrix[i][j] == 1 && matrix[i - 1][j] == 0) {
                    count++;
                }
            }
        }
    }
    
    printf("%d\n", count);
    
    return 0;
}

Time:O(R×C) - We iterate through each cell of the matrix once

Space:O(R×C) - We store the entire matrix in memory

Approach:

C Solution Explanation:

The C solution follows a straightforward approach:

Input Reading: Read R and C, then read the R×C matrix into a 2D array
Direction Processing: Read the sunlight direction character
Direction-Specific Logic: Based on the direction, iterate through the matrix and check adjacent cells:
- For 'L': Check if current cell has tree (1) and right neighbor is empty (0)
- For 'R': Check if current cell has tree (1) and left neighbor is empty (0)
- For 'B': Check if current cell has tree (1) and bottom neighbor is empty (0)
- For 'F': Check if current cell has tree (1) and top neighbor is empty (0)
Output: Print the total count of trees whose shadows fall on empty cells

The solution uses nested loops to traverse the matrix and simple conditional checks to determine shadow positions.

Visual Explanation

Loading diagram...

All Problems