Рубрики

Найти количество бесконечных точек

Динамическое программирование, Матрицы

Для заданной двоичной матрицы N x N нам нужно найти общее количество позиций матрицы, из которых идет бесконечный путь. Говорят, что любая позиция (i, j) имеет бесконечный путь, если и только если позиция (i, j) имеет значение 1, и все следующие позиции в ее строке (i) и ее столбце (j) должны иметь значение 1. Если любая позиция рядом с (i, j) в строке (i) или в столбце (j) будет иметь значение 0, то позиция (i, j) не имеет бесконечного пути.

Примеры:

Input :  0 1 0
         1 1 1
         0 1 1
Output : 4
Endless points are (1, 1), (1, 2),
(2, 1) and (2, 2). For all other
points path to some corner is 
blocked at some point.


Input :  0 1 1
         1 1 0
         0 1 0
Output : 1
Endless point is (0, 2).

Наивный подход:
Мы пересекаем все позиции, для каждой позиции мы проверяем, имеет ли эта позиция бесконечный путь или нет. Если да, то посчитайте, иначе проигнорируйте. Но, как обычно, сложность его времени кажется высокой.
Временная сложность: O (n 3 )

Advance Approach (Динамическое программирование):
Мы можем легко сказать, что если в любой позиции есть ноль, то он заблокирует путь для всех оставшихся позиций и вершины.

Также мы можем сказать, что любая позиция (i, j) будет иметь бесконечную строку, если (i, j + 1) будет иметь бесконечную строку и значение (i, j) равно 1.
Аналогично, мы можем сказать, что любая позиция (i, j) будет иметь бесконечный столбец, если (i + 1, j) будет иметь бесконечный столбец и значение (i, j) равно 1.

Таким образом, мы должны поддерживать две матрицы: одну для строки и одну для столбца. Всегда начинайте с самой правой позиции для строки и самой нижней позиции для столбца и проверяйте только следующую позицию, имеет ли она бесконечный путь или нет.
И наконец, если какая-либо позиция будет иметь бесконечный путь в матрице строк и столбцов, то эта позиция называется бесконечным путем.

C ++

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

using namespace std;

  

const int MAX = 100;

  
// Возвращает количество бесконечных точек

int countEndless(bool input[][MAX], int n)

{

    bool row[n][n], col[n][n];

  

    // Заполняет матрицу столбца. Для каждого столбца начните

    // из каждой последней строки и заполняем каждую запись как

    // блокировка после обнаружения 0

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

    {

        // флаг, который будет равен нулю, как только мы получим '0'

        // иначе будет 1

        bool isEndless = 1;

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

        {

            // встретил '0', установил isEndless

            // переменная в ложь

            if (input[i][j] == 0)

                isEndless = 0;

            col[i][j] = isEndless;

        }

    }

  

    // Аналогично, заполняем матрицу строк

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

    {

        bool isEndless = 1;

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

        {

            if (input[i][j] == 0)

                isEndless = 0;

            row[i][j] = isEndless;

        }

    }

  

    // Рассчитать общее количество бесконечных точек

    int ans = 0;

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

        for (int j=1; j<n; j++)

  

            // если в строке нет блокировки

            // или столбец после этой точки,

            // увеличиваем результат.

            if (row[i][j] && col[i][j])

                ans++;

  

    return ans;

}

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

int main()

{

    bool input[][MAX] = { {1, 0, 1, 1},

                         {0, 1, 1, 1},

                         {1, 1, 1, 1},

                         {0, 1, 1, 0}};

    int n = 4;

  

    cout << countEndless(input, n);

    return 0;

}

Джава

// Java программа для поиска количества бесконечных точек

class GFG {

      

    static final int MAX = 100;

      

    // Возвращает количество бесконечных точек

    static int countEndless(boolean input[][], int n)

    {

          

        boolean row[][] = new boolean[n][n];

        boolean col[][] = new boolean[n][n];

      

        // Заполняет матрицу столбца. Для каждого столбца

        // начинаем с каждой последней строки и заполняем каждую

        // запись как блокировка после обнаружения 0.

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

        {

              

            // флаг, который будет равен нулю, как только мы получим

            // a '0' и будет 1 в противном случае

            boolean isEndless = true;

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

            {

                  

                // встретил '0', установил

                // переменная isEndless в false

                if (input[i][j] == false)

                    isEndless = false;

                      

                col[i][j] = isEndless;

            }

        }

      

        // Аналогично, заполняем матрицу строк

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

        {

            boolean isEndless = true;

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

            {

                if (input[i][j] == false)

                    isEndless = false;

                row[i][j] = isEndless;

            }

        }

      

        // Рассчитать общее количество бесконечных точек

        int ans = 0;

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

            for (int j = 1; j < n; j++)

      

                // если в строке нет блокировки

                // или столбец после этой точки,

                // увеличиваем результат.

                if (row[i][j] && col[i][j])

                    ans++;

      

        return ans;

    }

      

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

    public static void main(String arg[])

    {

        boolean input[][] = { 

                    {true, false, true, true},

                    {false, true, true, true},

                    {true, true, true, true},

                    {false, true, true, false}};

        int n = 4;

      

        System.out.print(countEndless(input, n));

    }

}

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

python3

# Python3 программа для поиска количества
# бесконечные точки

import numpy as np

  
# Возвращает количество бесконечных точек

def countEndless(input_mat, n) :

  

    row = np.zeros((n, n))

    col = np.zeros((n, n))

  

    # Заполняет матрицу столбца. Для каждого столбца

    # начать с каждой последней строки и заполнить

    # каждая запись как блокировка после того, как найден 0.

    for j in range(n) :

          

        # флаг, который будет равен нулю, как только мы

        # получите '0', иначе будет 1

        isEndless = 1

          

        for i in range(n - 1, -1, -1) : 

          

            # обнаружил '0', установите

            # isEndless переменная в false

            if (input_mat[i][j] == 0) :

                isEndless = 0

              

            col[i][j] = isEndless

          

    # Аналогично заполняем матрицу строк

    for i in range(n) :

          

        isEndless = 1

        for j in range(n - 1, -1, -1) :

              

            if (input_mat[i][j] == 0) :

                isEndless = 0

                  

            row[i][j] = isEndless

          

    # Рассчитать общее количество бесконечных точек

    ans = 0

    for i in range(n) :

        for j in range(1, n) :

  

            # Если в строке нет блокировки

            # или столбец после этой точки,

            # приращение результата.

            #print (row [i] [j], col [i] [j])

            if (row[i][j] and col[i][j]) : 

                ans += 1

            #print (ANS)

  

    return ans

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

if __name__ == "__main__" : 

  

    input_mat = [[1, 0, 1, 1], 

                 [0, 1, 1, 1], 

                 [1, 1, 1, 1], 

                 [0, 1, 1, 0]] 

    n = 4

  

    print(countEndless(input_mat, n))

      
# Этот код предоставлен Ryuga

C #

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

using System;

  

public class GFG {

  

    // Возвращает количество бесконечных точек

    static int countEndless(bool [,]input, int n)

    {

          

        bool [,]row = new bool[n,n];

        bool [,]col = new bool[n,n];

      

        // Заполняет матрицу столбца. Для каждого

        // столбец, начинающийся с каждого последнего

        // строка и заполнить каждую запись как

        // блокировка после обнаружения 0

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

        {

              

            // флаг, который будет нулевым

            // как только мы получим 0 и

            // будет 1 в противном случае

            bool isEndless = true;

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

            {

                  

                // встретил '0', установил

                // переменная isEndless

                // в ложь

                if (input[i,j] == false)

                    isEndless = false;

                      

                col[i,j] = isEndless;

            }

        }

      

        // Аналогично, заполняем матрицу строк

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

        {

            bool isEndless = true;

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

            {

                if (input[i,j] == false)

                    isEndless = false;

                row[i,j] = isEndless;

            }

        }

      

        // Рассчитать общее количество

        // бесконечные точки

        int ans = 0;

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

            for (int j = 1; j < n; j++)

      

                // если нет блокировки

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

                // эта точка, приращение

                // результат.

                if (row[i,j] && col[i,j])

                    ans++;

      

        return ans;

    }

      

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

    public static void Main()

    {

        bool [,]input = { 

                {true, false, true, true},

                {false, true, true, true},

                {true, true, true, true},

                {false, true, true, false}};

        int n = 4;

      

        Console.Write(countEndless(input, n));

    }

}

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

PHP

<?php
// PHP программа для поиска
// количество бесконечных точек

  
// Возвращает количество
// бесконечные точки

function countEndless($input, $n)

{

  

    // Заполняет матрицу столбца. За

    // каждый столбец, начиная с

    // каждая последняя строка и заполнение

    // каждая запись как блокировка

    // после того, как 0 найден.

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

    {

        // флаг, который будет нулевым

        // как только мы получим '0' и

        // иначе будет 1

        $isEndless = 1;

        for ($i = $n - 1; $i >= 0; $i--)

        {

            // встретил '0',

            // устанавливаем isEndless

            // переменная в ложь

            if ($input[$i][$j] == 0)

                $isEndless = 0;

            $col[$i][$j] = $isEndless;

        }

    }

  

    // Аналогично, заполняем матрицу строк

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

    {

        $isEndless = 1;

        for ($j = $n - 1; $j >= 0; $j--)

        {

            if ($input[$i][$j] == 0)

                $isEndless = 0;

            $row[$i][$j] = $isEndless;

        }

    }

  

    // Рассчитать общее количество

    // бесконечных точек

    $ans = 0;

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

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

  

            // если нет блокировки

            // или столбец после этой точки,

            // увеличиваем результат.

            if ($row[$i][$j] && 

                $col[$i][$j])

                $ans++;

  

    return $ans;

}

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

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

               array(0, 1, 1, 1),

               array(1, 1, 1, 1),

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

$n = 4;

  

echo countEndless($input, $n);

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


Выход:

5

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

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

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

Найти количество бесконечных точек

0.00 (0%) 0 votes