Zig-Zag Robots

Simulate the movement of robots moving in alternating directions across rows and output their positions after T seconds

Understand the Problem

Problem Statement

There are R robots in R rows (one robot per row). There are two types of robots:

Type 1: Starts moving East, then alternates to West, then East, and so on
Type 2: Starts moving West, then alternates to East, then West, and so on

Each robot moves at 1 meter per second. Each row is C meters long. Given the initial positions and types of robots, print their positions after T seconds.

Constraints

2 ≤ R, C ≤ 50
1 ≤ T ≤ 10^4
0 indicates empty space
1 indicates Type 1 robot (starts East)
2 indicates Type 2 robot (starts West)
Each row has exactly one robot
Robot speed is 1 meter/second

Examples

Example 1

Input

5 6
0 0 0 0 1 0
0 0 2 0 0 0
0 0 0 2 0 0
1 0 0 0 0 0
0 0 0 0 0 2
3

Output

0 0 0 1 0 0
0 2 0 0 0 0
2 0 0 0 0 0
0 0 0 1 0 0
0 0 2 0 0 0

Explanation

After 3 seconds: - Type 1 robot in row 1 moves: 4→5→4→3 (position 3) - Type 2 robot in row 2 moves: 2→1→0→1 (position 1) - Type 2 robot in row 3 moves: 3→2→1→0 (position 0) - Type 1 robot in row 4 moves: 0→1→2→3 (position 3) - Type 2 robot in row 5 moves: 5→4→3→2 (position 2)

Example 2

Input

Output

Explanation

After 5 seconds: - Type 1 robot in row 1: 0→1→2→3→2→1 (position 1) - Type 1 robot in row 2: 1→2→3→2→1→0 (position 0) - Type 2 robot in row 3: 2→1→0→1→2→3 (position 3) - Type 2 robot in row 4: 3→2→1→0→1→2 (position 2)

Solution

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

int main() {
    int R, C, T;
    scanf("%d %d", &R, &C);
    
    int grid[50][50];
    int positions[50];  // positions[i] = column position of robot in row i
    int types[50];      // types[i] = 1 or 2 (robot type)
    int directions[50]; // directions[i] = +1 (East) or -1 (West)
    
    // Read grid and identify robots
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &grid[i][j]);
            if (grid[i][j] != 0) {
                positions[i] = j;
                types[i] = grid[i][j];
                directions[i] = (grid[i][j] == 1) ? 1 : -1;
            }
        }
    }
    
    scanf("%d", &T);
    
    // Simulate T seconds
    for (int t = 0; t < T; t++) {
        for (int i = 0; i < R; i++) {
            // Move robot one step
            positions[i] += directions[i];
            
            // Check if robot hit the wall and needs to reverse direction
            if (positions[i] < 0 || positions[i] >= C) {
                positions[i] -= directions[i];  // Move back
                directions[i] *= -1;           // Reverse direction
                positions[i] += directions[i];  // Move in new direction
            }
        }
    }
    
    // Output final grid
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (j == positions[i]) {
                printf("%d ", types[i]);
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
    
    return 0;
}

Time:O(R × T) - We process each robot for T seconds

Space:O(R × C) - Grid storage plus O(R) for robot tracking arrays

Approach:

C Solution Logic:

Input Reading: Read R, C, and the grid. Store robot positions, types, and initial directions.
Direction Setup: Type 1 robots start with direction +1 (East), Type 2 with -1 (West).
Simulation Loop: For each second, move each robot one step in its current direction.
Wall Detection: If a robot goes out of bounds, reverse its direction and move it back in bounds.
Output: After T seconds, reconstruct and print the final grid state.

The algorithm uses arrays to track robot state and simulates each second directly.

Visual Explanation

Loading diagram...

All Problems