Рубрики

Для булевой матрицы найдите k таким, что все элементы в k-й строке равны 0, а k-й столбец равны 1.

Для данной квадратной логической матрицы mat [n] [n] найдите k таким, что все элементы в k-й строке равны 0, а все элементы в k-м столбце равны 1. Значение mat [k] [k] может быть любым (либо 0, либо 1). Если такого k не существует, вернуть -1.

Примеры:

Input: bool mat[n][n] = { {1, 0, 0, 0},
                          {1, 1, 1, 0},
                          {1, 1, 0, 0},
                          {1, 1, 1, 0},
                        };
Output: 0
All elements in 0'th row are 0 and all elements in 
0'th column are 1.  mat[0][0] is 1 (can be any value)


Input: bool mat[n][n] = {{0, 1, 1, 0, 1},
                         {0, 0, 0, 0, 0},
                         {1, 1, 1, 0, 0},
                         {1, 1, 1, 1, 0},
                         {1, 1, 1, 1, 1}};
Output: 1
All elements in 1'st row are 0 and all elements in 
1'st column are 1.  mat[1][1] is 0 (can be any value)


Input: bool mat[n][n] = {{0, 1, 1, 0, 1},
                         {0, 0, 0, 0, 0},
                         {1, 1, 1, 0, 0},
                         {1, 0, 1, 1, 0},
                         {1, 1, 1, 1, 1}};
Output: -1
There is no k such that k'th row elements are 0 and
k'th column elements are 1.

Ожидаемая сложность времени O (n)

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Простое решение — проверить все строки одну за другой. Если мы находим строку 'i' так, что все элементы этой строки равны 0, кроме mat [i] [i], который может быть 0 или 1, то мы проверяем все значения в столбце 'i'. Если все значения равны 1 в столбце, мы возвращаем i. Временная сложность этого решения составляет O (n 2 ).

Эффективное решение может решить эту проблему за O (n) время. Решение основано на следующих фактах.
1) Может быть не более одного k, который можно квалифицировать как ответ (Почему? Обратите внимание, что если в k-й строке есть все 0, возможно, кроме mat [k] [k], то ни один столбец не может иметь все 1 ′) s ,
2) Если мы пройдем указанную матрицу из угла (предпочтительно сверху справа и снизу слева), мы можем быстро отказаться от полной строки или полного столбца на основе приведенных ниже правил.
… .A) Если mat [i] [j] равен 0 и i! = J, то столбец j не может быть решением.
… .B) Если mat [i] [j] равен 1 и i! = J, то строка i не может быть решением.

Ниже приведен полный алгоритм, основанный на вышеуказанных наблюдениях.

1) Start from top right corner, i.e., i = 0, j = n-1.  
   Initialize result as -1.

2) Do following until we find the result or reach outside the matrix.

......a) If mat[i][j] is 0, then check all elements on left of j in current row. 
.........If all elements on left of j are also 0, then set result as i. Note 
.........that i may not be result, but if there is a result, then it must be i 
.........(Why? we reach mat[i][j] after discarding all rows above it and all 
.........columns on right of it)

.........If all left side elements of i'th row are not 0, them this row cannot 
.........be a solution, increment i.

......b) If mat[i][j] is 1, then check all elements below i in current column. 
.........If all elements below i are 1, then set result as j. Note that j may
......... not be result, but if there is a result, then it must be j 

.........If all elements of j'th column are not 1, them this column cannot be a
.........solution decrement j.

3) If result is -1, return it. 

4) Else check validity of result by checking all row and column
          elements of result

Ниже приведена реализация, основанная на представленной выше идее.

C ++

// C ++ программа, чтобы найти меня таким, чтобы все записи в i-й строке были 0
// и все записи в столбце i't равны 1
#include <iostream>

using namespace std;

#define n 5

  

int find(bool arr[n][n])

{

    // Начинаем с самого верхнего правого угла

    // (Мы могли бы начать и с других углов)

    int i=0, j=n-1;

  

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

    int res = -1;

  

    // Найти индекс (этот цикл выполняется не более 2n раз, мы либо

    // увеличиваем номер строки или уменьшаем номер столбца)

    while (i<n && j>=0)

    {

        // Если текущий элемент равен 0, то эта строка может быть решением

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

        {

            // Проверяем все элементы в этой строке

            while (j >= 0 && (arr[i][j] == 0 || i == j))

                j--;

  

            // Если все значения равны 0, сохраняем эту строку как результат

            if (j == -1)

            {

                res = i;

                break;

            }

  

            // Мы достигаем здесь, если мы нашли 1 в текущей строке, так что это

            // строка не может быть решением, увеличить номер строки

            else i++;

        }

        else // Если текущий элемент равен 1

        {

            // Проверяем все элементы в этом столбце

            while (i<n && (arr[i][j] == 1 || i == j))

                i++;

  

            // Если все элементы равны 1

            if (i == n)

            {

                res = j;

                break;

            }

  

            // Мы достигаем здесь, если мы нашли 0 в текущем столбце, так что это

            // столбец не может быть решением, увеличить номер столбца

            else j--;

        }

    }

  

    // Если мы не смогли найти результат в вышеуказанном цикле, то результат не существует

    if (res == -1)

       return res;

  

    // Проверяем, верен ли рассчитанный выше res

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

       if (res != i && arr[i][res] != 1)

          return -1;

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

       if (res != j && arr[res][j] != 0)

          return -1;

  

    return res;

}

  

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

int main()

{

    bool mat[n][n] = {{0, 0, 1, 1, 0},

                      {0, 0, 0, 1, 0},

                      {1, 1, 1, 1, 0},

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

                      {1, 1, 1, 1, 1}};

    cout << find(mat);

  

    return 0;

}

Джава

// Java-программа, чтобы найти меня таким, чтобы все записи в i-й строке были 0
// и все записи в столбце i't равны 1

class GFG {

  

    static int n = 5;

  

    static int find(boolean arr[][]) {

        // Начинаем с самого верхнего правого угла

        // (Мы могли бы начать и с других углов)

        int i = 0, j = n - 1;

  

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

        int res = -1;

  

        // Найти индекс (этот цикл выполняется не более 2n раз, мы либо

        // увеличиваем номер строки или уменьшаем номер столбца)

        while (i < n && j >= 0) {

            // Если текущий элемент имеет значение false, то эта строка может быть решением

            if (arr[i][j] == false) {

                // Проверяем все элементы в этой строке

                while (j >= 0 && (arr[i][j] == false || i == j)) {

                    j--;

                }

  

                // Если все значения ложные, то сохраняем эту строку как результат

                if (j == -1) {

                    res = i;

                    break;

                } // Мы достигаем здесь, если мы нашли 1 в текущей строке, так что это

                // строка не может быть решением, увеличить номер строки

                else {

                    i++;

                }

            } else // Если текущий элемент равен 1

            {

                // Проверяем все элементы в этом столбце

                while (i < n && (arr[i][j] == true || i == j)) {

                    i++;

                }

  

                // Если все элементы равны 1

                if (i == n) {

                    res = j;

                    break;

                } // Мы достигаем здесь, если мы нашли 0 в текущем столбце, так что это

                // столбец не может быть решением, увеличить номер столбца

                else {

                    j--;

                }

            }

        }

  

        // Если мы не смогли найти результат в вышеуказанном цикле, то результат не существует

        if (res == -1) {

            return res;

        }

  

        // Проверяем, верен ли рассчитанный выше res

        for (int k = 0; k < n; k++) {

            if (res != k && arr[k][res] != true) {

                return -1;

            }

        }

        for (int l = 0; l < n; l++) {

            if (res != l && arr[res][l] != false) {

                return -1;

            }

        }

  

        return res;

    }

  

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

    public static void main(String[] args) {

        boolean mat[][] = {{false, false, true, true, false},

        {false, false, false, true, false},

        {true, true, true, true, false},

        {false, false, false, false, false},

        {true, true, true, true, true}};

        System.out.println(find(mat));

    }

}

  
/ * Этот код Java предоставлен PrinciRaj1992 * /

питон

'' 'Программа Python, чтобы найти k таким, что все элементы в k-й строке

    0 и k-й столбец 1 '' '

  

def find(arr):

  

    # хранить длину массива

    n = len(arr)

  

    # начать с верхнего правого угла

    i = 0

    j = n - 1

      

    # инициализировать результат

    res = -1

  

    # найти индекс (этот цикл выполняется максимум 2n раз, мы

    # увеличение номера строки или уменьшение номера столбца)

    while i < n and j >= 0:

  

        # если текущий элемент равен 0, то эта строка может быть решением

        if arr[i][j] == 0:

  

            # проверить все элементы в этой строке

            while j >= 0 and (arr[i][j] == 0 or i == j):

                j -= 1

  

            # если все значения равны 0, обновить результат как номер строки

            if j == -1:

                res = i

                break

  

            # если найдено 1 в текущей строке, строка не может быть

            # решение, увеличить номер строки

            else: i += 1

  

        # если текущий элемент равен 1

        else:

  

            # проверить все элементы в этом столбце

            while i < n and (arr[i][j] == 1 or i == j):

                i +=1

  

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

            if i == n:

                res = j

                break

  

            # если найдено 0 в текущем столбце, столбец не может быть

            # решение, уменьшение номера столбца

            else: j -= 1

  

    # если мы не смогли найти результат в вышеуказанном цикле, результат не существует

    if res == -1:

        return res

  

    # проверить, является ли указанное выше значение res действительным

    for i in range(0, n):

        if res != i and arr[i][res] != 1:

            return -1

    for j in range(0, j):

        if res != j and arr[res][j] != 0:

            return -1;

   

    return res;

  
# test find (arr) функция

arr = [ [0,0,1,1,0],

         [0,0,0,1,0],

         [1,1,1,1,0],

         [0,0,0,0,0],

         [1,1,1,1,1] ]

  

print find(arr)

C #

// C # программа, чтобы найти меня таким, чтобы все записи в i-й строке были 0
// и все записи в столбце i't равны 1

  

using System;

public class GFG{

  

    static int n = 5; 

  

    static int find(bool [,]arr) { 

        // Начинаем с самого верхнего правого угла

        // (Мы могли бы начать и с других углов)

        int i = 0, j = n - 1; 

  

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

        int res = -1; 

  

        // Найти индекс (этот цикл выполняется не более 2n раз, мы либо

        // увеличиваем номер строки или уменьшаем номер столбца)

        while (i < n && j >= 0) { 

            // Если текущий элемент имеет значение false, то эта строка может быть решением

            if (arr[i,j] == false) { 

                // Проверяем все элементы в этой строке

                while (j >= 0 && (arr[i,j] == false || i == j)) { 

                    j--; 

                

  

                // Если все значения ложные, то сохраняем эту строку как результат

                if (j == -1) { 

                    res = i; 

                    break

                } // Мы достигаем здесь, если мы нашли 1 в текущей строке, так что это

                // строка не может быть решением, увеличить номер строки

                else

                    i++; 

                

            } else // Если текущий элемент равен 1

            

                // Проверяем все элементы в этом столбце

                while (i < n && (arr[i,j] == true || i == j)) { 

                    i++; 

                

  

                // Если все элементы равны 1

                if (i == n) { 

                    res = j; 

                    break

                } // Мы достигаем здесь, если мы нашли 0 в текущем столбце, так что это

                // столбец не может быть решением, увеличить номер столбца

                else

                    j--; 

                

            

        

  

        // Если мы не смогли найти результат в вышеуказанном цикле, то результат не существует

        if (res == -1) { 

            return res; 

        

  

        // Проверяем, верен ли рассчитанный выше res

        for (int k = 0; k < n; k++) { 

            if (res != k && arr[k,res] != true) { 

                return -1; 

            

        

        for (int l = 0; l < n; l++) { 

            if (res != l && arr[res,l] != false) { 

                return -1; 

            

        

  

        return res; 

    

  

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

    public static void Main() { 

        bool [,]mat = {{false, false, true, true, false}, 

        {false, false, false, true, false}, 

        {true, true, true, true, false}, 

        {false, false, false, false, false}, 

        {true, true, true, true, true}}; 

        Console.WriteLine(find(mat)); 

    

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

PHP

<?php
// PHP программа, чтобы найти меня таким, чтобы все
// записи в i-й строке равны 0 и все
// записи в i-ом столбце 1

  

function find(&$arr)

{

    $n = 5;

      

    // Начинаем с самого верхнего правого угла

    // (Мы могли бы начать и с других углов)

    $i = 0;

    $j = $n - 1;

  

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

    $res = -1;

  

    // Найти индекс (Этот цикл выполняется максимум

    // 2 раза, мы либо увеличиваем номер строки

    // или уменьшение номера столбца)

    while ($i < $n && $j >= 0)

    {

        // Если текущий элемент равен 0, то этот

        // строка может быть решением

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

        {

            // Проверяем все элементы в этой строке

            while ($j >= 0 && ($arr[$i][$j] == 0 || 

                                        $i == $j))

                $j--;

  

            // Если все значения равны 0, то сохраняем

            // эта строка как результат

            if ($j == -1)

            {

                $res = $i;

                break;

            }

  

            // Мы достигаем здесь, если мы нашли 1 в текущем

            // строка, поэтому эта строка не может быть решением,

            // увеличиваем номер строки

            else

            $i++;

        }

        else // Если текущий элемент равен 1

        {

            // Проверяем все элементы в этом столбце

            while ($i < $n && ($arr[$i][$j] == 1 || 

                                        $i == $j))

                $i++;

  

            // Если все элементы равны 1

            if ($i == $n)

            {

                $res = $j;

                break;

            }

  

            // Мы достигаем здесь, если мы нашли 0 в текущем

            // столбец, поэтому этот столбец не может быть решением,

            // увеличить номер столбца

            else

            $j--;

        }

    }

  

    // Если мы не смогли найти результат выше

    // цикл, тогда результат не существует

    if ($res == -1)

    return $res;

  

    // Проверяем, верен ли рассчитанный выше res

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

    if ($res != $i && $arr[$i][$res] != 1)

        return -1;

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

    if ($res != $j && $arr[$res][$j] != 0)

        return -1;

  

    return $res;

}

  

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

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

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

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

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

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

echo (find($mat));

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


Выход:

3

Временная сложность этого решения составляет O (n). Обратите внимание, что мы пересекаем не более 2n элементов в главном цикле while.

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

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

Для булевой матрицы найдите k таким, что все элементы в k-й строке равны 0, а k-й столбец равны 1.

0.00 (0%) 0 votes