Рубрики

Общий охват всех нулей в двоичной матрице

Для заданной двоичной матрицы, которая содержит только 0 и 1, нам нужно найти сумму покрытия всех нулей матрицы, где покрытие для конкретного 0 определяется как общее число единиц около нуля слева, справа, вверх и нижние направления. Они могут быть где угодно до угла в направлении.
Примеры:

Input : mat[][] = {0 0 0 0
                   1 0 0 1
                   0 1 1 0
                   0 1 0 0}
Output : 20
First four zeros are surrounded by only 
one 1.  So coverage for zeros in first 
row is 1 + 1 + 1 + 1
Zeros in second row are surrounded by
three 1's. Note that there is no 1 above.
There are 1's in all other three directions.
Coverage of zeros in second row = 3 + 3. 
Similarly counting for others also, we get
overall count as below.
1 + 1 + 1 + 1 + 3 + 3 + 2 + 2 + 2 + 2 + 2 = 20

Input : mat[][] = {1 1 1 0
                   1 0 0 1}
Output : 8
Coverage of first zero is 2
Coverages of other two zeros is 3
Total coverage = 2 + 3 + 3 = 8

Простое решение этой проблемы — подсчет единиц вокруг нулей независимо, т.е. мы запускаем цикл четыре раза в каждом направлении для каждой ячейки для данной матрицы. Всякий раз, когда мы находим 1 в любом цикле, мы разбиваем цикл и увеличиваем результат на 1.

Эффективное решение заключается в следующем.

  1. Обходите все строки слева направо, увеличивайте результат, если 1 уже видна (в текущем обходе), а текущий элемент равен 0.
  2. Обходите все строки справа налево, увеличивайте результат, если 1 уже видна (в текущем обходе), а текущий элемент равен 0.
  3. Обходите все столбцы сверху вниз, увеличивайте результат, если 1 уже видна (в текущем обходе), а текущий элемент равен 0.
  4. Обходите все столбцы снизу вверх, увеличивайте результат, если 1 уже видна (в текущем обходе), а текущий элемент равен 0.

В приведенном ниже коде используется булева переменная isOne, которая становится истинной, как только в текущем обходе встречается единица, для всех нулей после этой итерации результат увеличивается на единицу, во всех четырех направлениях применяется одинаковая процедура для получения окончательного ответа. , Мы сбрасываем isOne в false после каждого обхода.

C ++

// C ++ программа для получения полного покрытия всех нулей в
// двоичная матрица
#include <bits/stdc++.h>

using namespace std;

#define R 4
#define C 4

  
// Возвращает общее покрытие всех нулей в mat [] []

int getTotalCoverageOfMatrix(int mat[R][C])

{

    int res = 0;

  

    // цикл для всех строк матрицы

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

    {

        bool isOne = false// 1 еще не видел

  

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

        // направление, чтобы получить левые

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

        {

            // Если один найден слева

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

                isOne = true;

  

            // Если 0 найдено и мы нашли

            // 1 раньше.

            else if (isOne)

                res++;

        }

  

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

        // левое направление.

        isOne = false;

        for (int j = C-1; j >= 0; j--)

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

    }

  

    // Перемещение через столбцы вверх и вниз

    // направления.

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

    {

        bool isOne = false// 1 еще не видел

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

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

  

        isOne = false;

        for (int i = R-1; i >= 0; i--)

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

    }

    return res;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

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

        {1, 0, 0, 1},

        {0, 1, 1, 0},

        {0, 1, 0, 0}

    };

  

    cout << getTotalCoverageOfMatrix(mat);

  

    return 0;

}

Джава

// Java программа для получения итогов
// охват всех нулей в
// двоичная матрица

import java .io.*;

  

class GFG 

{

static int R = 4;

static int C = 4;

  
// Возвращает общее покрытие
// всех нулей в мате [] []

static int getTotalCoverageOfMatrix(int [][]mat)

{

    int res = 0;

  

    // цикл для всех

    // строки матрицы

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

    {

        // 1 еще не видел

        boolean isOne = false

  

        // цикл в столбцах из

        // слева направо

        // чтобы оставить левых

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

        {

            // Если он найден

            // слева

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

                isOne = true;

  

            // Если найден 0 и мы

            // нашли 1 раньше.

            else if (isOne)

                res++;

        }

  

        // Повторим выше

        // процесс для права

        // влево.

        isOne = false;

        for (int j = C - 1; j >= 0; j--)

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

    }

  

    // Обход колонн

    // для направления вверх и вниз.

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

    {

        // 1 еще не видел

        boolean isOne = false

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

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

  

        isOne = false;

        for (int i = R - 1; i >= 0; i--)

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

    }

    return res;

}

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

static public void main (String[] args)

{

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

                   {1, 0, 0, 1},

                   {0, 1, 1, 0},

                   {0, 1, 0, 0}};

  
System.out.println(

           getTotalCoverageOfMatrix(mat));

}
}

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

C #

// C # программа для получения полного покрытия
// всех нулей в двоичной матрице

using System;

  

class GFG {

      

static int R = 4;

static int C = 4;

  
// Возвращает общее покрытие всех нулей в mat [] []

static int getTotalCoverageOfMatrix(int [,]mat)

{

    int res = 0;

  

    // цикл для всех строк матрицы

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

    {

        // 1 еще не видел

        bool isOne = false

  

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

        // правильное направление, чтобы получить левые

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

        {

            // Если один найден слева

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

                isOne = true;

  

            // Если найден 0 и мы

            // нашли 1 раньше.

            else if (isOne)

                res++;

        }

  

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

        // справа налево.

        isOne = false;

        for (int j = C-1; j >= 0; j--)

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

    }

  

    // Обход колонн

    // для направления вверх и вниз.

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

    {

        // 1 еще не видел

        bool isOne = false

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

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

  

        isOne = false;

        for (int i = R-1; i >= 0; i--)

        {

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

                isOne = true;

            else if (isOne)

                res++;

        }

    }

    return res;

}

  
// Код драйвера для тестирования вышеуказанных методов

    static public void Main ()

    {

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

                      {1, 0, 0, 1},

                      {0, 1, 1, 0},

                      {0, 1, 0, 0}};

  

    Console.WriteLine(getTotalCoverageOfMatrix(mat));

    }

}

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


Выход:

20

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

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Общий охват всех нулей в двоичной матрице

0.00 (0%) 0 votes