Robot Movements

Count the number of left, right, up, and down movements of a robot navigating from the top-left to the bottom-right of a matrix

Understand the Problem

Problem Statement

Robot Movements: A robot movement in a R*C matrix (R rows and C columns) filled with asterisks is recorded using the following characters.
– indicates left or right movement
| indicates up or down movement
The program must print the number of times the robot moved left, right, up and down. The robot will not visit the same cell twice. The robot always starts from the top left cell of the matrix and ends at the bottom right cell. The input will be in the format so that more than one movement will not be possible from a given cell.

Constraints

2 ≤ R, C ≤ 50
The robot starts at position (0,0) and ends at position (R-1, C-1)
The robot will not visit the same cell twice
From any given cell, at most one valid movement is possible
Matrix contains only characters: '-', '|', '*'

Examples

Example 1

Input

5 6
– – | * * *
| – – * – |
– – – – | |
* * * * * |
* * * * * *

Output

2 7 1 5

Explanation

The robot follows the unique path from top-left to bottom-right, making 2 left moves, 7 right moves, 1 up move, and 5 down moves.

Example 2

Input

3 4
– | * *
| – * *
– – – *

Output

1 4 0 2

Explanation

The robot moves from (0,0) to (2,3) following the path: right, right, right, right, down, down, with 1 left move.

Solution

#include <stdio.h>
#include <stdlib.h>

int left = 0, right = 0, up = 0, down = 0;

void dfs(int r, int c, char arr[r][c], int i, int j, int L, int R, int U, int D) {
    // Reached destination
    if (i == r - 1 && j == c - 1) {
        left = L;
        right = R;
        up = U;
        down = D;
        return;
    }
    
    // Out of bounds or blocked/visited cell
    if (i < 0 || j < 0 || i >= r || j >= c || arr[i][j] == '*') {
        return;
    }
    
    char current = arr[i][j];
    arr[i][j] = '*'; // Mark as visited
    
    if (current == '|') {
        // Move up
        dfs(r, c, arr, i - 1, j, L, R, U + 1, D);
        // Move down
        dfs(r, c, arr, i + 1, j, L, R, U, D + 1);
    } else if (current == '-') {
        // Move left
        dfs(r, c, arr, i, j - 1, L + 1, R, U, D);
        // Move right
        dfs(r, c, arr, i, j + 1, L, R + 1, U, D);
    }
    
    arr[i][j] = current; // Restore for backtracking
}

int main() {
    int r, c;
    scanf("%d %d", &r, &c);
    
    char arr[r][c];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf(" %c", &arr[i][j]);
        }
    }
    
    dfs(r, c, arr, 0, 0, 0, 0, 0, 0);
    printf("%d %d %d %d", left, right, up, down);
    return 0;
}

Time:O(R*C) - Each cell is visited at most once

Space:O(R*C) - Due to recursion stack depth in worst case

Approach:

Step-by-step explanation:
1. Global variables track movement counts
2. dfs() function performs depth-first search from current position
3. Base case: when we reach bottom-right cell, store the counts
4. Boundary check: return if out of bounds or cell is blocked/visited
5. Mark current cell as visited by changing to '*'
6. If current cell is '|', recursively explore up and down directions
7. If current cell is '-', recursively explore left and right directions
8. After exploring, restore original character for backtracking
9. Main function reads input and calls dfs() from start position
10. Finally prints the accumulated movement counts

Visual Explanation

Loading diagram...

All Problems