Рубрики

Учитывая матрицу 'O' и 'X', замените 'O' на 'X', если окружено 'X'

Учитывая матрицу, в которой каждый элемент представляет собой «O» или «X», замените «O» на «X», если он окружен «X». «O» (или набор «O») считается окруженным «X», если есть «X» в точках чуть ниже, чуть выше, слева и справа от него.

Примеры:

Input: mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };
Output: mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                      {'X', 'O', 'X', 'X', 'X', 'X'},
                      {'X', 'X', 'X', 'X', 'X', 'X'},
                      {'O', 'X', 'X', 'X', 'X', 'X'},
                      {'X', 'X', 'X', 'O', 'X', 'O'},
                      {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Input: mat[M][N] =  {{'X', 'X', 'X', 'X'}
                     {'X', 'O', 'X', 'X'}
                     {'X', 'O', 'O', 'X'}
                     {'X', 'O', 'X', 'X'}
                     {'X', 'X', 'O', 'O'}
                    };
Input: mat[M][N] =  {{'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'X', 'X'}
                     {'X', 'X', 'O', 'O'}
                    };

Это в основном применение алгоритма Flood-Fill . Основное отличие здесь состоит в том, что «O» не заменяется на «X», если оно лежит в области, которая заканчивается на границе. Ниже приведены простые шаги для выполнения этой специальной заливки.

1) Пройдите по данной матрице и замените все «O» специальным символом «-».

2) Пройдите четыре ребра заданной матрицы и вызовите floodFill ('-', 'O') для каждого '-' на ребрах. Остальные «-» — это символы, обозначающие «О» (в исходной матрице), которые должны быть заменены на «Х».

3) Пройдите по матрице и замените все «-и» на «Х».

Давайте рассмотрим шаги приведенного выше алгоритма на примере.
Позвольте следующим будет входная матрица.

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Шаг 1: Заменить все «O» на «-».

       mat[M][N] =  {{'X', '-', 'X', 'X', 'X', 'X'},
                     {'X', '-', 'X', 'X', '-', 'X'},
                     {'X', 'X', 'X', '-', '-', 'X'},
                     {'-', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', '-', 'X', '-'},
                     {'-', '-', 'X', '-', '-', '-'},
                    };

Шаг 2: Вызовите floodFill ('-', 'O') для всех краевых элементов со значением, равным '-'

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', '-', 'X'},
                     {'X', 'X', 'X', '-', '-', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Шаг 3: Заменить все «-» на «X».

       mat[M][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'X', 'X', 'X'},
                     {'O', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                     {'O', 'O', 'X', 'O', 'O', 'O'},
                    };

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// Программа на C ++ для замены всех «O» на «X», если они окружены «X»
#include<iostream>

using namespace std;

  
// Размер данной матрицы равен MXN
#define M 6
#define N 6

  

  
// Рекурсивная функция для замены предыдущего значения 'prevV' в '(x, y)'
// и все окружающие значения (x, y) с новым значением 'newV'.

void floodFillUtil(char mat[][N], int x, int y, char prevV, char newV)

{

    // Базовые случаи

    if (x < 0 || x >= M || y < 0 || y >= N)

        return;

    if (mat[x][y] != prevV)

        return;

  

    // Заменить цвет на (x, y)

    mat[x][y] = newV;

  

    // Повторение на север, восток, юг и запад

    floodFillUtil(mat, x+1, y, prevV, newV);

    floodFillUtil(mat, x-1, y, prevV, newV);

    floodFillUtil(mat, x, y+1, prevV, newV);

    floodFillUtil(mat, x, y-1, prevV, newV);

}

  
// Возвращает размер матрицы максимального размера
// в окружении 'X'

int replaceSurrounded(char mat[][N])

{

   // Шаг 1: заменить все «O» на «-»

   for (int i=0; i<M; i++)

      for (int j=0; j<N; j++)

          if (mat[i][j] == 'O')

             mat[i][j] = '-';

  

   // Вызовите floodFill для всех '-' лежащих по краям

   for (int i=0; i<M; i++)   // Левая сторона

      if (mat[i][0] == '-')

        floodFillUtil(mat, i, 0, '-', 'O');

   for (int i=0; i<M; i++)  // Правая сторона

      if (mat[i][N-1] == '-')

        floodFillUtil(mat, i, N-1, '-', 'O');

   for (int i=0; i<N; i++)   // Верхняя сторона

      if (mat[0][i] == '-')

        floodFillUtil(mat, 0, i, '-', 'O');

   for (int i=0; i<N; i++)  // Нижняя сторона

      if (mat[M-1][i] == '-')

        floodFillUtil(mat, M-1, i, '-', 'O');

  

   // Шаг 3: Заменить все '-' на 'X'

   for (int i=0; i<M; i++)

      for (int j=0; j<N; j++)

         if (mat[i][j] == '-')

             mat[i][j] = 'X';

  
}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char mat[][N] =  {{'X', 'O', 'X', 'O', 'X', 'X'},

                     {'X', 'O', 'X', 'X', 'O', 'X'},

                     {'X', 'X', 'X', 'O', 'X', 'X'},

                     {'O', 'X', 'X', 'X', 'X', 'X'},

                     {'X', 'X', 'X', 'O', 'X', 'O'},

                     {'O', 'O', 'X', 'O', 'O', 'O'},

                    };

    replaceSurrounded(mat);

  

  

    for (int i=0; i<M; i++)

    {

      for (int j=0; j<N; j++)

          cout << mat[i][j] << " ";

      cout << endl;

    }

    return 0;

}

Джава

// Java-программа для замены
// все 'O' с 'X', если
// в окружении 'X'

import java.io.*;

  

class GFG

{

    static int M = 6;

    static int N = 6;

    static void floodFillUtil(char mat[][], int x, 

                              int y, char prevV, 

                              char newV)

    {

        // Базовые случаи

        if (x < 0 || x >= M ||

            y < 0 || y >= N)

            return;

              

        if (mat[x][y] != prevV)

            return;

      

        // Заменить цвет на (x, y)

        mat[x][y] = newV;

      

        // Повторение на север,

        // восток, юг и запад

        floodFillUtil(mat, x + 1, y, 

                      prevV, newV);

        floodFillUtil(mat, x - 1, y, 

                      prevV, newV);

        floodFillUtil(mat, x, y + 1

                      prevV, newV);

        floodFillUtil(mat, x, y - 1

                      prevV, newV);

    }

      

    // Возвращает размер максимума

    // размер субквадратной матрицы

    // в окружении 'X'

    static void replaceSurrounded(char mat[][])

    {

          

    // Шаг 1: заменить

    // все 'O' с '-'

    for (int i = 0; i < M; i++)

        for (int j = 0; j < N; j++)

            if (mat[i][j] == 'O')

                mat[i][j] = '-';

      

    // Вызовите floodFill для

    // все '-' лежат по краям

    for (int i = 0; i < M; i++) // Левая сторона

        if (mat[i][0] == '-')

            floodFillUtil(mat, i, 0

                          '-', 'O');

    for (int i = 0; i < M; i++) // Правая сторона

        if (mat[i][N - 1] == '-')

            floodFillUtil(mat, i, N - 1,

                          '-', 'O');

    for (int i = 0; i < N; i++) // Верхняя сторона

        if (mat[0][i] == '-')

            floodFillUtil(mat, 0, i,

                          '-', 'O');

    for (int i = 0; i < N; i++) // Нижняя сторона

        if (mat[M - 1][i] == '-')

            floodFillUtil(mat, M - 1

                          i, '-', 'O');

      

    // Шаг 3: заменить

    // все '-' с 'X'

    for (int i = 0; i < M; i++)

        for (int j = 0; j < N; j++)

            if (mat[i][j] == '-')

                mat[i][j] = 'X';

    }

      

    // Код драйвера

    public static void main (String[] args)

    {

        char[][] mat = {{'X', 'O', 'X'

                         'O', 'X', 'X'},

                        {'X', 'O', 'X'

                         'X', 'O', 'X'},

                        {'X', 'X', 'X'

                         'O', 'X', 'X'},

                        {'O', 'X', 'X',

                         'X', 'X', 'X'},

                        {'X', 'X', 'X',

                         'O', 'X', 'O'},

                        {'O', 'O', 'X',

                         'O', 'O', 'O'}};

                          

        replaceSurrounded(mat);

      

        for (int i = 0; i < M; i++)

        {

            for (int j = 0; j < N; j++)

                System.out.print(mat[i][j] + " "); 

                  

            System.out.println("");

        }

    }

}

  
// Этот код добавлен
// от shiv_bhakt

C #

// AC # программа для замены
// все 'O' с 'X', если
// в окружении 'X'

using System;

  

class GFG

{

    static int M = 6;

    static int N = 6;

    static void floodFillUtil(char [,]mat, int x, 

                              int y, char prevV, 

                              char newV)

    {

        // Базовые случаи

        if (x < 0 || x >= M ||

            y < 0 || y >= N)

            return;

              

        if (mat[x, y] != prevV)

            return;

      

        // Заменить цвет на (x, y)

        mat[x, y] = newV;

       

        // Повторение на север,

        // восток, юг и запад

        floodFillUtil(mat, x + 1, y, 

                       prevV, newV);

        floodFillUtil(mat, x - 1, y, 

                       prevV, newV);

        floodFillUtil(mat, x, y + 1, 

                       prevV, newV);

        floodFillUtil(mat, x, y - 1, 

                       prevV, newV);

    }

      

    // Возвращает размер максимума

    // размер субквадратной матрицы

    // в окружении 'X'

    static void replaceSurrounded(char [,]mat)

    {

          

    // Шаг 1: заменить

    // все 'O' с '-'

    for (int i = 0; i < M; i++)

        for (int j = 0; j < N; j++)

            if (mat[i, j] == 'O')

                mat[i, j] = '-';

      

    // Вызовите floodFill для

    // все '-' лежат по краям

    for (int i = 0; i < M; i++) // Левая сторона

        if (mat[i, 0] == '-')

            floodFillUtil(mat, i, 0, 

                          '-', 'O');

    for (int i = 0; i < M; i++) // Правая сторона

        if (mat[i, N - 1] == '-')

            floodFillUtil(mat, i, N - 1,

                          '-', 'O');

    for (int i = 0; i < N; i++) // Верхняя сторона

        if (mat[0, i] == '-')

            floodFillUtil(mat, 0, i,

                          '-', 'O');

    for (int i = 0; i < N; i++) // Нижняя сторона

        if (mat[M - 1, i] == '-')

            floodFillUtil(mat, M - 1, 

                          i, '-', 'O');

      

    // Шаг 3: заменить

    // все '-' с 'X'

    for (int i = 0; i < M; i++)

        for (int j = 0; j < N; j++)

            if (mat[i, j] == '-')

                mat[i, j] = 'X';

    }

      

    // Код драйвера

    public static void Main ()

    {

        char [,]mat = new char[,]

                        {{'X', 'O', 'X'

                          'O', 'X', 'X'},

                         {'X', 'O', 'X'

                          'X', 'O', 'X'},

                         {'X', 'X', 'X'

                          'O', 'X', 'X'},

                         {'O', 'X', 'X',

                          'X', 'X', 'X'},

                         {'X', 'X', 'X',

                          'O', 'X', 'O'},

                         {'O', 'O', 'X',

                          'O', 'O', 'O'}};

                          

        replaceSurrounded(mat);

      

        for (int i = 0; i < M; i++)

        {

            for (int j = 0; j < N; j++)

                Console.Write(mat[i, j] + " "); 

                  

            Console.WriteLine("");

        }

    }

}

  
// Этот код добавлен
// от shiv_bhakt

PHP

<?php 
// PHP программа для замены всех
// 'O с' X ', если они окружены' X '

  
// Размер данного
// матрица MXN

$M = 6;

$N = 6;

  

  
// Рекурсивная функция для замены
// предыдущее значение prevV в at (x, y)
// и все окружающие значения
// (x, y) с новым значением 'newV'.

function floodFillUtil(&$mat, $x, $y

                        $prevV, $newV)

{

    // Базовые случаи

    if ($x < 0 || $x >= $GLOBALS['M'] || 

        $y < 0 || $y >= $GLOBALS['N'])

        return;

    if ($mat[$x][$y] != $prevV)

        return;

  

    // Заменить цвет на (x, y)

    $mat[$x][$y] = $newV;

  

    // Повторение на север,

    // восток, юг и запад

    floodFillUtil($mat, $x + 1, $y, $prevV, $newV);

    floodFillUtil($mat, $x - 1, $y, $prevV, $newV);

    floodFillUtil($mat, $x, $y + 1, $prevV, $newV);

    floodFillUtil($mat, $x, $y - 1, $prevV, $newV);

}

  
// Возвращает размер максимума
// размер субквадратной матрицы
// в окружении 'X'

function replaceSurrounded(&$mat)

{

      
// Шаг 1: заменить все «O» на «-»

for ($i = 0; $i < $GLOBALS['M']; $i++)

    for ($j = 0; $j < $GLOBALS['N']; $j++)

        if ($mat[$i][$j] == 'O')

            $mat[$i][$j] = '-';

  
// Вызовите floodFill для всех
// '-' лежащий по краям

for ($i = 0; 

     $i < $GLOBALS['M']; $i++) // Левая сторона

    if ($mat[$i][0] == '-')

        floodFillUtil($mat, $i, 0, '-', 'O');

          

for ($i = 0; $i < $GLOBALS['M']; $i++) // Правая сторона

    if ($mat[$i][$GLOBALS['N'] - 1] == '-')

        floodFillUtil($mat, $i,

                      $GLOBALS['N'] - 1, '-', 'O');

          

for ($i = 0; $i < $GLOBALS['N']; $i++) // Верхняя сторона

    if ($mat[0][$i] == '-')

        floodFillUtil($mat, 0, $i, '-', 'O');

          

for ($i = 0; $i < $GLOBALS['N']; $i++) // Нижняя сторона

    if ($mat[$GLOBALS['M'] - 1][$i] == '-')

        floodFillUtil($mat, $GLOBALS['M'] - 1, 

                            $i, '-', 'O');

  
// Шаг 3: Заменить все '-' на 'X'

for ($i = 0; $i < $GLOBALS['M']; $i++)

    for ($j = 0; $j < $GLOBALS['N']; $j++)

        if ($mat[$i][$j] == '-')

            $mat[$i][$j] = 'X';

  
}

  
// Код драйвера

$mat = array(array('X', 'O', 'X', 'O', 'X', 'X'),

             array('X', 'O', 'X', 'X', 'O', 'X'),

             array('X', 'X', 'X', 'O', 'X', 'X'),

             array('O', 'X', 'X', 'X', 'X', 'X'),

             array('X', 'X', 'X', 'O', 'X', 'O'),

             array('O', 'O', 'X', 'O', 'O', 'O'));

replaceSurrounded($mat);

  

for ($i = 0; $i < $GLOBALS['M']; $i++)

{

    for ($j = 0; $j < $GLOBALS['N']; $j++)

        echo $mat[$i][$j]." ";

    echo "\n";

}

  
// Этот код предоставлен ChitraNayal
?>


Выход:

X O X O X X 
X O X X X X 
X X X X X X 
O X X X X X 
X X X O X O 
O O X O O O 

Временная сложность вышеуказанного решения составляет O (MN). Обратите внимание, что каждый элемент матрицы обрабатывается не более трех раз.

Эта статья предоставлена Anmol . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Учитывая матрицу 'O' и 'X', замените 'O' на 'X', если окружено 'X'

0.00 (0%) 0 votes