Surrounded Regions - C Solution

1. Introduction

In this post, we explore a matrix manipulation problem known as "Surrounded Regions". The challenge involves identifying regions in a matrix that are fully surrounded by a certain character and then modifying those regions. This problem is a good example of depth-first search (DFS) application in a matrix context in C programming.

Problem

Given an m x n matrix board containing 'X' and 'O', the task is to capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.

2. Solution Steps

1. Iterate over the matrix. For each 'O' on the border, perform a DFS to mark all connected 'O's as safe.

2. Iterate over the matrix again. For each 'O' not marked as safe, flip it to 'X'.

3. Convert all safe-marked 'O's back to regular 'O's.

4. Return the modified matrix.

3. Code Program

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

void dfs(char** board, int boardSize, int* boardColSize, int row, int col) {
    if (row < 0 || col < 0 || row >= boardSize || col >= boardColSize[row] || board[row][col] != 'O') {
        return;
    }

    // Mark the current 'O' as safe
    board[row][col] = 'S';

    // Perform DFS in all four directions
    dfs(board, boardSize, boardColSize, row + 1, col);
    dfs(board, boardSize, boardColSize, row - 1, col);
    dfs(board, boardSize, boardColSize, row, col + 1);
    dfs(board, boardSize, boardColSize, row, col - 1);
}

void solve(char** board, int boardSize, int* boardColSize) {
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            if (i == 0 || j == 0 || i == boardSize - 1 || j == boardColSize[i] - 1) {
                if (board[i][j] == 'O') {
                    dfs(board, boardSize, boardColSize, i, j);
                }
            }
        }
    }

    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] == 'S') {
                board[i][j] = 'O';
            }
        }
    }
}

// Main function to test the solve function
int main() {
    char* board[] = {
        "XXXX",
        "XOOX",
        "XXOX",
        "XOXX"
    };
    int boardSize = 4;
    int boardColSize[] = {4, 4, 4, 4};

    solve(board, boardSize, boardColSize);

    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            printf("%c", board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Output:

XXXX
XXXX
XXXX
XOXX

Explanation:

1. solve function first marks 'O's on the border and all connected 'O's as safe ('S') using DFS.

2. In the second pass, it flips all unmarked 'O's to 'X's and converts safe 'O's back to regular 'O's.

3. The main function demonstrates this process with a sample matrix.