Рубрики

Вопрос о булевой матрице

Учитывая булеву матрицу mat [M] [N] размера MXN, измените ее так, чтобы, если mat ячейки матрицы [i] [j] равен 1 (или true), тогда все ячейки i-й строки и j-го столбца делаются на 1.

Example 1
The matrix
1 0
0 0
should be changed to following
1 1
1 0

Example 2
The matrix
0 0 0
0 0 1
should be changed to following
0 0 1
1 1 1

Example 3
The matrix
1 0 0 1
0 0 1 0
0 0 0 0
should be changed to following
1 1 1 1
1 1 1 1
1 0 1 1

Способ 1 (использовать два временных массива)
1) Создайте два временных массива row [M] и col [N]. Инициализируйте все значения row [] и col [] как 0.
2) Пройдите через матрицу ввода [M] [N]. Если вы видите запись mat [i] [j] как true, пометьте row [i] и col [j] как true.
3) Пройдите через матрицу ввода снова [M] [N]. Для каждой записи mat [i] [j] проверьте значения строки [i] и col [j]. Если какое-либо из двух значений (row [i] или col [j]) имеет значение true, пометьте mat [i] [j] как true.

Спасибо Dixit Sethi за предложение этого метода.

C ++

// Код C ++ для вопроса о булевой матрице
#include <bits/stdc++.h>

  

using namespace std;

#define R 3
#define C 4

  

void modifyMatrix(bool mat[R][C])

{

    bool row[R];

    bool col[C];

  

    int i, j;

      

    / * Инициализировать все значения строки [] как 0 * /

    for (i = 0; i < R; i++)

    {

    row[i] = 0;

    }

  

    / * Инициализировать все значения col [] как 0 * /

    for (i = 0; i < C; i++)

    {

    col[i] = 0;

    }

  

    // Сохраняем строки и столбцы, которые будут помечены как

    // 1 в массивах row [] и col [] соответственно

    for (i = 0; i < R; i++)

    {

        for (j = 0; j < C; j++)

        {

            if (mat[i][j] == 1)

            {

                row[i] = 1;

                col[j] = 1;

            }

        }

    }

  

    // Модифицируем матрицу ввода mat [] используя

    // над построенными массивами row [] и col []

    for (i = 0; i < R; i++)

    {

        for (j = 0; j < C; j++)

        {

            if ( row[i] == 1 || col[j] == 1 )

            {

                mat[i][j] = 1;

            }

        }

    }

}

  
/ * Утилита для печати 2D-матрицы * /

void printMatrix(bool mat[R][C])

{

    int i, j;

    for (i = 0; i < R; i++)

    {

        for (j = 0; j < C; j++)

        {

            cout << mat[i][j];

        }

        cout << endl;

    }

}

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

int main()

{

    bool mat[R][C] = { {1, 0, 0, 1},

                       {0, 0, 1, 0},

                       {0, 0, 0, 0}};

  

    cout << "Input Matrix \n";

    printMatrix(mat);

  

    modifyMatrix(mat);

  

    printf("Matrix after modification \n");

    printMatrix(mat);

  

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

Джава

// Java-код для вопроса о булевой матрице

class GFG

{

    public static void modifyMatrix(int mat[ ][ ], int R, int C)

    {

        int row[ ]= new int [R];

        int col[ ]= new int [C];

        int i, j;

      

        / * Инициализировать все значения строки [] как 0 * /

        for (i = 0; i < R; i++)

        {

        row[i] = 0;

        }

      

      

        / * Инициализировать все значения col [] как 0 * /

        for (i = 0; i < C; i++)

        {

        col[i] = 0;

        }

      

      

        / * Сохранить строки и столбцы, которые будут помечены как

        1 в массивах row [] и col [] соответственно * /

        for (i = 0; i < R; i++)

        {

            for (j = 0; j < C; j++)

            {

                if (mat[i][j] == 1)

                {

                    row[i] = 1;

                    col[j] = 1;

                }

            }

        }

      

        / * Изменить матрицу ввода [], используя

        построенные выше массивы row [] и col [] * /

        for (i = 0; i < R; i++)

        {

            for (j = 0; j < C; j++)

            {

                if ( row[i] == 1 || col[j] == 1 )

                {

                    mat[i][j] = 1;

                }

            }

        }

    }

      

    / * Утилита для печати 2D-матрицы * /

    public static void printMatrix(int mat[ ][ ], int R, int C)

    {

        int i, j;

        for (i = 0; i < R; i++)

        {

            for (j = 0; j < C; j++)

            {

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

            }

            System.out.println();

        }

    }

      

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

    public static void main(String[] args) 

    {

        int mat[ ][ ] = { {1, 0, 0, 1},

                          {0, 0, 1, 0},

                          {0, 0, 0, 0},};

                      

                System.out.println("Matrix Intially");

                  

                printMatrix(mat, 3, 4);

              

                modifyMatrix(mat, 3, 4);

                System.out.println("Matrix after modification n");

                printMatrix(mat, 3, 4);

              

    

  
}

  
// Этот код предоставлен Камалем Равалом

python3

Код Python3 для вопроса о булевой матрице

R = 3

C = 4

  

def modifyMatrix(mat):

    row = [0] *

    col = [0] *

      

    # Инициализировать все значения строки [] как 0

    for i in range(0, R):

        row[i] = 0

          

    # Инициализировать все значения col [] как 0

    for i in range(0, C) :

        col[i] = 0

  

  

    # Хранить строки и столбцы, которые будут отмечены

    # как 1 в массивах row [] и col [] соответственно

    for i in range(0, R) :

          

        for j in range(0, C) :

            if (mat[i][j] == 1) :

                row[i] = 1

                col[j] = 1

              

    # Изменить матрицу ввода [], используя

    # выше построенных массивов row [] и col []

    for i in range(0, R) :

          

        for j in range(0, C):

            if ( row[i] == 1 or col[j] == 1 ) :

                mat[i][j] = 1

                  
# Полезная функция для печати 2D-матрицы

def printMatrix(mat) :

    for i in range(0, R):

          

        for j in range(0, C) :

            print(mat[i][j], end = " ")

        print()

          
Код водителя

mat = [ [1, 0, 0, 1],

        [0, 0, 1, 0],

        [0, 0, 0, 0] ] 

  

print("Input Matrix n")

printMatrix(mat)

  
modifyMatrix(mat)

  

print("Matrix after modification n")

printMatrix(mat)

  
# Этот код предоставлен Никитой Тивари.

C #

// C # код для логического
// Матрица Вопрос

using System;

  

class GFG

{

    public static void modifyMatrix(int [,]mat, 

                                    int R, int C)

    {

        int []row = new int [R];

        int []col = new int [C];

        int i, j;

      

        / * Инициализировать все значения

        строки [] как 0 * /

        for (i = 0; i < R; i++)

        {

        row[i] = 0;

        }

      

      

        / * Инициализировать все значения

        col [] как 0 * /

        for (i = 0; i < C; i++)

        {

        col[i] = 0;

        }

      

      

        / * Сохранить строки и столбцы

        быть отмеченным как 1 в строке []

        и col [] массивы соответственно * /

        for (i = 0; i < R; i++)

        {

            for (j = 0; j < C; j++)

            {

                if (mat[i, j] == 1)

                {

                    row[i] = 1;

                    col[j] = 1;

                }

            }

        }

      

        / * Изменить матрицу ввода

        коврик [] с использованием вышеуказанного

        построенный ряд [] и

        col [] массивы * /

        for (i = 0; i < R; i++)

        {

            for (j = 0; j < C; j++)

            {

                if (row[i] == 1 || col[j] == 1)

                {

                    mat[i, j] = 1;

                }

            }

        }

    }

      

    / * Полезная функция для

    распечатать 2D матрицу * /

    public static void printMatrix(int [,]mat, 

                                   int R, int C)

    {

        int i, j;

        for (i = 0; i < R; i++)

        {

            for (j = 0; j < C; j++)

            {

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

            }

            Console.WriteLine();

        }

    }

      

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

    static public void Main ()

    {

        int [,]mat = {{1, 0, 0, 1},

                      {0, 0, 1, 0},

                      {0, 0, 0, 0}};

              

        Console.WriteLine("Matrix Intially");

          

        printMatrix(mat, 3, 4);

      

        modifyMatrix(mat, 3, 4);

        Console.WriteLine("Matrix after "+

                        "modification n");

        printMatrix(mat, 3, 4);

          

    }

}

  
// Этот код предоставлен ajit

PHP

<?php 
// PHP-код для логического
// Матрица Вопрос

$R = 3;

$C = 4;

  

function modifyMatrix(&$mat)

{

    global $R,$C;

    $row = array();

    $col = array();

  

    / * Инициализировать все значения

       строки [] как 0 * /

    for ($i = 0; $i < $R; $i++)

    {

        $row[$i] = 0;

    }

  

  

    / * Инициализировать все значения

       col [] как 0 * /

    for ($i = 0; $i < $C; $i++)

    {

        $col[$i] = 0;

    }

  

  

    / * Сохранить строки и столбцы

       быть отмеченным как 1 в строке []

       и col [] массивы соответственно * /

    for ($i = 0; $i < $R; $i++)

    {

        for ($j = 0; $j < $C; $j++)

        {

            if ($mat[$i][$j] == 1)

            {

                $row[$i] = 1;

                $col[$j] = 1;

            }

        }

    }

  

    / * Изменить матрицу ввода []

       используя вышеизложенное

       массивы row [] и col [] * /

    for ($i = 0; $i < $R; $i++)

    {

        for ($j = 0; $j < $C; $j++)

        {

            if ($row[$i] == 1 || 

                $col[$j] == 1 )

            {

                $mat[$i][$j] = 1;

            }

        }

    }

}

  
/ * Полезная функция для

   распечатать 2D матрицу * /

function printMatrix(&$mat)

{

    global $R, $C;

    for ($i = 0; $i < $R; $i++)

    {

        for ($j = 0; $j < $C; $j++)

        {

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

        }

        echo "\n";

    }

}

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

$mat = array(array(1, 0, 0, 1),

             array(0, 0, 1, 0),

             array(0, 0, 0, 0));

  

echo "Input Matrix \n";

printMatrix($mat);

  

modifyMatrix($mat);

  

echo "Matrix after modification \n";

printMatrix($mat);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Input Matrix
1 0 0 1
0 0 1 0
0 0 0 0
Matrix after modification
1 1 1 1
1 1 1 1
1 0 1 1

Сложность времени: O (M * N)
Вспомогательное пространство: O (M + N)

Метод 2 (Пространственно оптимизированная версия метода 1)
Этот метод является оптимизированной по пространству версией вышеупомянутого метода 1. Этот метод использует первую строку и первый столбец входной матрицы вместо вспомогательных массивов row [] и col [] метода 1. Итак, что мы делаем: сначала возьмем заботиться о первой строке и столбце и хранить информацию об этих двух переменных в двух флаговых переменных rowFlag и colFlag. Получив эту информацию, мы можем использовать первую строку и первый столбец в качестве вспомогательных массивов и применить метод 1 для подматрицы (матрицы, исключая первую строку и первый столбец) размера (M-1) * (N-1).

1) Просканируйте первую строку и установите переменную rowFlag, чтобы указать, нужно ли нам устанавливать все 1 в первой строке или нет.
2) Сканируйте первый столбец и установите переменную colFlag, чтобы указать, нужно ли нам устанавливать все 1 в первом столбце или нет.
3) Используйте первую строку и первый столбец в качестве вспомогательных массивов row [] и col [] соответственно, рассмотрите матрицу как подматрицу, начиная со второй строки и второго столбца, и примените метод 1.
4) Наконец, используя rowFlag и colFlag, при необходимости обновите первую строку и первый столбец.

Сложность времени: O (M * N)
Вспомогательное пространство: O (1)

Спасибо Сидху за предложение этого метода.

C ++

#include <bits/stdc++.h>

using namespace std;

#define R 3
#define C 4

  

void modifyMatrix(int mat[R][C])

{

    // переменные, чтобы проверить, есть ли 1

    // в первой строке и столбце

    bool row_flag = false;

    bool col_flag = false;

  

    // обновляем первую строку и столбец, если 1

    // встречается

    for (int i = 0; i < R; i++) {

        for (int j = 0; j < C; j++) {

            if (i == 0 && mat[i][j] == 1)

                row_flag = true;

  

            if (j == 0 && mat[i][j] == 1)

                col_flag = true;

  

            if (mat[i][j] == 1) {

  

                mat[0][j] = 1;

                mat[i][0] = 1;

            }

        }

    }

  

    // Модифицируем матрицу ввода mat [] используя

    // первая строка и первый столбец Matrix mat

    for (int i = 1; i < R; i++) {

        for (int j = 1; j < C; j++) {

  

            if (mat[0][j] == 1 || mat[i][0] == 1) {

                mat[i][j] = 1;

            }

        }

    }

  

    // изменить первую строку, если она была 1

    if (row_flag == true) {

        for (int i = 0; i < C; i++) {

            mat[0][i] = 1;

        }

    }

  

    // изменить первый столбец, если он был 1

    if (col_flag == true) {

        for (int i = 0; i < R; i++) {

            mat[i][0] = 1;

        }

    }

}

  
/ * Утилита для печати 2D-матрицы * /

void printMatrix(int mat[R][C])

{

    for (int i = 0; i < R; i++) {

        for (int j = 0; j < C; j++) {

            cout << mat[i][j];

        }

        cout << "\n";

    }

}

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

int main()

{

  

    int mat[R][C] = { { 1, 0, 0, 1 },

                      { 0, 0, 1, 0 },

                      { 0, 0, 0, 0 } };

  

    cout << "Input Matrix :\n";

    printMatrix(mat);

  

    modifyMatrix(mat);

  

    cout << "Matrix After Modification :\n";

    printMatrix(mat);

    return 0;

}

  
// Этот код предоставлен Никитой Тивари

Джава

class GFG

    public static void modifyMatrix(int mat[][]){

                  

        // переменные, чтобы проверить, есть ли 1

        // в первой строке и столбце

        boolean row_flag = false;

        boolean col_flag = false;

                  

        // обновляем первую строку и столбец, если 1

        // встречается

        for (int i = 0; i < mat.length; i++ ){

                for (int j = 0; j < mat[0].length; j++){

                        if (i == 0 && mat[i][j] == 1)

                            row_flag = true;

                          

                        if (j == 0 && mat[i][j] == 1)

                            col_flag = true;

                          

                        if (mat[i][j] == 1){

                              

                            mat[0][j] = 1;

                            mat[i][0] = 1;

                        }

                          

                    }

                }

                  

        // Модифицируем матрицу ввода mat [] используя

        // первая строка и первый столбец Matrix mat

        for (int i = 1; i < mat.length; i ++){

                for (int j = 1; j < mat[0].length; j ++){

                          

                    if (mat[0][j] == 1 || mat[i][0] == 1){

                            mat[i][j] = 1;

                        }

                    }

                }

                  

        // изменить первую строку, если она была 1

        if (row_flag == true){

            for (int i = 0; i < mat[0].length; i++){

                        mat[0][i] = 1;

                    }

                }

                  

        // изменить первый столбец, если он был 1

        if (col_flag == true){

            for (int i = 0; i < mat.length; i ++){

                        mat[i][0] = 1;

            }

        }

    }

              

    / * Утилита для печати 2D-матрицы * /

    public static void printMatrix(int mat[][]){

        for (int i = 0; i < mat.length; i ++){

            for (int j = 0; j < mat[0].length; j ++){

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

            }

                System.out.println("");

        }

    }

              

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

    public static void main(String args[] ){

                  

        int mat[][] = {{1, 0, 0, 1},

                {0, 0, 1, 0},

                {0, 0, 0, 0}};

                  

        System.out.println("Input Matrix :");

        printMatrix(mat);

              

        modifyMatrix(mat);

              

        System.out.println("Matrix After Modification :");

        printMatrix(mat);

              

    }

}

  
// Этот код предоставлен Арнавом Кр. Мандал.

python3

Код Python3 для вопроса о булевой матрице

def modifyMatrix(mat) :

      

    # переменные, чтобы проверить, есть ли 1

    # в первой строке и столбце

    row_flag = False

    col_flag = False

              

    # обновление первой строки и столбца

    # если встречается 1

    for i in range(0, len(mat)) :

          

        for j in range(0, len(mat)) :

            if (i == 0 and mat[i][j] == 1) :

                row_flag = True

                      

            if (j == 0 and mat[i][j] == 1) :

                col_flag = True

              

            if (mat[i][j] == 1) :

                mat[0][j] = 1

                mat[i][0] = 1

                  

    # Изменить матрицу ввода [], используя

    # первая строка и первый столбец Matrix mat

    for i in range(1, len(mat)) :

          

        for j in range(1, len(mat) + 1) :

            if (mat[0][j] == 1 or mat[i][0] == 1) :

                mat[i][j] = 1

                  

    # изменить первую строку, если она была 1

    if (row_flag == True) :

        for i in range(0, len(mat)) :

            mat[0][i] = 1

              

    # изменить первый столбец, если он был 1

    if (col_flag == True) :

        for i in range(0, len(mat)) :

            mat[i][0] = 1

              
# Полезная функция для печати 2D-матрицы

def printMatrix(mat) :

      

    for i in range(0, len(mat)) :

        for j in range(0, len(mat) + 1) :

            print( mat[i][j], end = "" )

          

        print()

          
Код водителя

mat = [ [1, 0, 0, 1],

        [0, 0, 1, 0],

        [0, 0, 0, 0] ]

          

print("Input Matrix :")

printMatrix(mat)

      
modifyMatrix(mat)

      

print("Matrix After Modification :")

printMatrix(mat)

  
# Этот код предоставлен Никитой Тивари.

C #

// C # код для логического
// Матрица Вопрос

using System;

  

class GFG

    public static void modifyMatrix(int[,] mat)

    {

                  

        // переменные для проверки

        // если есть 1

        // в первой строке и столбце

        bool row_flag = false;

        bool col_flag = false;

                  

        // обновляем первый

        // строка и столбец, если 1

        // встречается

        for (int i = 0;

                 i < mat.GetLength(0); i++ )

        {

                for (int j = 0; 

                         j < mat.GetLength(1); j++)

                {

                        if (i == 0 && mat[i, j] == 1)

                            row_flag = true;

                          

                        if (j == 0 && mat[i, j] == 1)

                            col_flag = true;

                          

                        if (mat[i, j] == 1)

                        {

                            mat[0, j] = 1;

                            mat[i,0] = 1;

                        }

                          

                    }

                }

                  

        // Модифицируем матрицу ввода mat []

        // используя первый ряд и первый

        // столбец Matrix mat

        for (int i = 1; 

                 i < mat.GetLength(0); i ++)

        {

                for (int j = 1; 

                         j < mat.GetLength(1); j ++)

                {

                          

                    if (mat[0, j] == 1 || 

                        mat[i, 0] == 1)

                    {

                            mat[i, j] = 1;

                        }

                    }

                }

                  

        // изменить первый ряд

        // если был 1

        if (row_flag == true)

        {

            for (int i = 0; 

                     i < mat.GetLength(1); i++)

            {

                        mat[0, i] = 1;

            }

        }

                  

        // изменить первый столбец, если

        // был 1

        if (col_flag == true)

        {

            for (int i = 0; 

                     i < mat.GetLength(0); i ++)

            {

                        mat[i, 0] = 1;

            }

        }

    }

              

    / * Функция полезности

    распечатать 2D матрицу * /

    public static void printMatrix(int[,] mat)

    {

        for (int i = 0; 

                 i < mat.GetLength(0); i ++)

        {

            for (int j = 0; 

                     j < mat.GetLength(1); j ++)

            {

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

            }

                Console.Write("\n");

        }

    }

              

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

    public static void Main()

    {

        int[,] mat = {{1, 0, 0, 1},

                      {0, 0, 1, 0},

                      {0, 0, 0, 0}};

                  

        Console.Write("Input Matrix :\n");

        printMatrix(mat);

              

        modifyMatrix(mat);

              

        Console.Write("Matrix After "

                      "Modification :\n");

        printMatrix(mat);

    }

}

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

PHP

<?php 
// PHP-код для логического
// Матрица Вопрос

$R = 3;

$C = 4;

  

function modifyMatrix(&$mat)

{

    global $R, $C;

      

    // переменные для проверки

    // есть 1 в

    // первая строка и столбец

    $row_flag = false;

    $col_flag = false;

  

    // обновляем первый

    // строка и столбец, если 1

    // встречается

    for ($i = 0; $i < $R; $i++) 

    {

        for ($j = 0; $j < $C; $j++) 

        {

            if ($i == 0 && $mat[$i][$j] == 1)

                $row_flag = true;

  

            if ($j == 0 && $mat[$i][$j] == 1)

                $col_flag = true;

  

            if ($mat[$i][$j] == 1) 

            {

                $mat[0][$j] = 1;

                $mat[$i][0] = 1;

            }

        }

    }

  

    // Изменить матрицу ввода

    // mat [] используя первый

    // строка и первый столбец

    // Матричный коврик

    for ($i = 1; $i < $R; $i++) 

    {

        for ($j = 1; $j < $C; $j++)

        {

            if ($mat[0][$j] == 1 || 

                $mat[$i][0] == 1)

            {

                $mat[$i][$j] = 1;

            }

        }

    }

  

    // изменить первый ряд

    // если был 1

    if ($row_flag == true) 

    {

        for ($i = 0; $i < $C; $i++)

        {

            $mat[0][$i] = 1;

        }

    }

  

    // изменить первый столбец

    // если был 1

    if ($col_flag == true) 

    {

        for ($i = 0; $i < $R; $i++)

        {

            $mat[$i][0] = 1;

        }

    }

}

  
/ * Функция полезности
распечатать 2D матрицу * /

function printMatrix(&$mat)

{

    global $R, $C;

    for ($i = 0; $i < $R; $i++) 

    {

        for ($j = 0; $j < $C; $j++)

        {

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

        }

        echo "\n";

    }

}

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

$mat = array(array(1, 0, 0, 1 ),

             array(0, 0, 1, 0 ),

             array(0, 0, 0, 0 ));

  

echo "Input Matrix :\n";

printMatrix($mat);

  

modifyMatrix($mat);

  

echo "Matrix After Modification :\n";

printMatrix($mat);

  
// Этот код приписан
// ChitraNayal
?>


Выход:

Input Matrix :
1001
0010
0000
Matrix After Modification :
1111
1111
1011

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

Вопрос о булевой матрице

0.00 (0%) 0 votes