Forest Fire – TCS CodeVita

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 21

// Structure to represent a position in the grid
struct Point {
    int x, y;
};

// Queue structure for BFS
struct Queue {
    int front, rear, size;
    struct Point* array;
};

// Function to create a queue
struct Queue* createQueue(int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (struct Point*)malloc(capacity * sizeof(struct Point));
    return queue;
}

// Function to check if queue is full
int isFull(struct Queue* queue) {
    return (queue->size == MAX_SIZE * MAX_SIZE);
}

// Function to check if queue is empty
int isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

// Function to enqueue an item
void enqueue(struct Queue* queue, struct Point item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
}

// Function to dequeue an item
struct Point dequeue(struct Queue* queue) {
    struct Point item = {0, 0};
    if (isEmpty(queue))
        return item;
    item = queue->array[queue->front];
    queue->front = (queue->front + 1) % MAX_SIZE;
    queue->size = queue->size - 1;
    return item;
}

// Function to check if a position is valid
int isValid(int x, int y, int m, int n) {
    return (x >= 1 && x <= m && y >= 1 && y <= n);
}

// Function to solve the forest fire problem
int solveForestFire(char forest[MAX_SIZE][MAX_SIZE], int m, int n, int startX, int startY) {
    // Directions for 8 adjacent positions
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    // Create queue for BFS
    struct Queue* queue = createQueue(MAX_SIZE * MAX_SIZE);
    
    // Visited array to track burned trees
    int visited[MAX_SIZE][MAX_SIZE] = {0};
    
    // Start BFS from the initial burning tree
    struct Point start = {startX, startY};
    enqueue(queue, start);
    visited[startX][startY] = 1;
    
    int minutes = 0;
    int totalTrees = 0;
    int burnedTrees = 0;
    
    // Count total trees in the forest
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (forest[i][j] == 'T') {
                totalTrees++;
            }
        }
    }
    
    // BFS to spread fire
    while (!isEmpty(queue)) {
        int currentLevelSize = queue->size;
        
        // Process all trees that catch fire in this minute
        for (int i = 0; i < currentLevelSize; i++) {
            struct Point current = dequeue(queue);
            burnedTrees++;
            
            // Spread fire to all 8 adjacent trees
            for (int dir = 0; dir < 8; dir++) {
                int newX = current.x + dx[dir];
                int newY = current.y + dy[dir];
                
                if (isValid(newX, newY, m, n) && 
                    forest[newX][newY] == 'T' && 
                    !visited[newX][newY]) {
                    visited[newX][newY] = 1;
                    struct Point next = {newX, newY};
                    enqueue(queue, next);
                }
            }
        }
        
        // If there are more trees to burn, increment minutes
        if (queue->size > 0) {
            minutes++;
        }
    }
    
    free(queue->array);
    free(queue);
    
    return minutes;
}

int main() {
    int m, n;
    int startX, startY;
    char forest[MAX_SIZE][MAX_SIZE];
    
    // Read input dimensions
    scanf("%d %d", &m, &n);
    
    // Read starting position
    scanf("%d %d", &startX, &startY);
    
    // Read forest layout
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf(" %c", &forest[i][j]);
        }
    }
    
    // Solve and print result
    int result = solveForestFire(forest, m, n, startX, startY);
    printf("%d\n", result);
    
    return 0;
}