# 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.

## Comments

## Post a Comment