이진 행렬의 모든 0에 대한 전체 적용 범위

GfG Practice에서 사용해 보세요. ' title=

#practiceLinkDiv { 표시: 없음 !중요; }

0과 1만 포함하는 이진 행렬이 주어지면 특정 0에 대한 적용 범위는 왼쪽 오른쪽 위쪽 및 아래쪽 방향에서 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

Recommended Practice 이진 행렬의 모든 0 범위 시도해 보세요!

에이 간단한 해결책 이 문제를 해결하려면 독립적으로 0 주위의 1을 계산해야 합니다. 즉, 주어진 행렬의 각 셀에 대해 각 방향으로 루프를 4번 실행합니다. 루프에서 1을 발견할 때마다 루프를 중단하고 결과를 1씩 증가시킵니다.

안 효율적인 솔루션 다음을 수행하는 것입니다.

1이 이미 표시되고(현재 순회에서) 현재 요소가 0인 경우 왼쪽에서 오른쪽 증분 결과로 모든 행을 순회합니다.
현재 순회에서 1이 이미 표시되고 현재 요소가 0인 경우 모든 행을 오른쪽에서 왼쪽으로 순회합니다.
1이 이미 표시되고(현재 순회에서) 현재 요소가 0인 경우 위에서 아래 증분 결과로 모든 열을 순회합니다.
현재 순회에서 1이 이미 표시되고 현재 요소가 0인 경우 모든 열을 아래에서 위로 증가 결과로 순회합니다.

아래 코드에서는 부울 변수 isOne이 사용되며, 이는 최종 응답을 얻기 위해 네 방향 모두에 적용되는 하나의 동일한 절차에 의해 반복 결과가 증가된 후 모든 0에 대한 현재 순회에서 1이 발견되자마자 true가 됩니다. 매 순회 후에 isOne을 false로 재설정합니다.

C++

// C++ program to get total coverage of all zeros in // a binary matrix #include    using namespace std; #define R 4 #define C 4 // Returns total coverage of all zeros in mat[][] int getTotalCoverageOfMatrix(int mat[R][C]) {  int res = 0;  // looping for all rows of matrix  for (int i = 0; i < R; i++)  {  bool isOne = false; // 1 is not seen yet  // looping in columns from left to right  // direction to get left ones  for (int j = 0; j < C; j++)  {  // If one is found from left  if (mat[i][j] == 1)  isOne = true;  // If 0 is found and we have found  // a 1 before.  else if (isOne)  res++;  }  // Repeat the above process for right to  // left direction.  isOne = false;  for (int j = C-1; j >= 0; j--)  {  if (mat[i][j] == 1)  isOne = true;  else if (isOne)  res++;  }  }  // Traversing across columns for up and down  // directions.  for (int j = 0; j < C; j++)  {  bool isOne = false; // 1 is not seen yet  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; } // Driver code to test above methods 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

// Java program to get total  // coverage of all zeros in  // a binary matrix import java .io.*; class GFG  { static int R = 4; static int C = 4; // Returns total coverage // of all zeros in mat[][] static int getTotalCoverageOfMatrix(int [][]mat) {  int res = 0;  // looping for all   // rows of matrix  for (int i = 0; i < R; i++)  {  // 1 is not seen yet  boolean isOne = false;   // looping in columns from   // left to right direction  // to get left ones  for (int j = 0; j < C; j++)  {  // If one is found  // from left  if (mat[i][j] == 1)  isOne = true;  // If 0 is found and we   // have found a 1 before.  else if (isOne)  res++;  }  // Repeat the above   // process for right   // to left direction.  isOne = false;  for (int j = C - 1; j >= 0; j--)  {  if (mat[i][j] == 1)  isOne = true;  else if (isOne)  res++;  }  }  // Traversing across columns  // for up and down directions.  for (int j = 0; j < C; j++)  {  // 1 is not seen yet  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; } // Driver code  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)); } } // This code is contributed by anuj_67.

Python3

# Python3 program to get total coverage of all zeros in # a binary matrix R = 4 C = 4 # Returns total coverage of all zeros in mat[][] def getTotalCoverageOfMatrix(mat): res = 0 # looping for all rows of matrix for i in range(R): isOne = False # 1 is not seen yet # looping in columns from left to right # direction to get left ones for j in range(C): # If one is found from left if (mat[i][j] == 1): isOne = True # If 0 is found and we have found # a 1 before. else if (isOne): res += 1 # Repeat the above process for right to # left direction. isOne = False for j in range(C - 1 -1 -1): if (mat[i][j] == 1): isOne = True else if (isOne): res += 1 # Traversing across columns for up and down # directions. for j in range(C): isOne = False # 1 is not seen yet for i in range(R): if (mat[i][j] == 1): isOne = True else if (isOne): res += 1 isOne = False for i in range(R - 1 -1 -1): if (mat[i][j] == 1): isOne = True else if (isOne): res += 1 return res # Driver code mat = [[0 0 0 0][1 0 0 1][0 1 1 0][0 1 0 0]] print(getTotalCoverageOfMatrix(mat)) # This code is contributed by shubhamsingh10

// C# program to get total coverage  // of all zeros in a binary matrix using System; class GFG {   static int R = 4; static int C = 4; // Returns total coverage of all zeros in mat[][] static int getTotalCoverageOfMatrix(int []mat) {  int res = 0;  // looping for all rows of matrix  for (int i = 0; i < R; i++)  {  // 1 is not seen yet  bool isOne = false;   // looping in columns from left to   // right direction to get left ones  for (int j = 0; j < C; j++)  {  // If one is found from left  if (mat[ij] == 1)  isOne = true;  // If 0 is found and we   // have found a 1 before.  else if (isOne)  res++;  }  // Repeat the above process for   // right to left direction.  isOne = false;  for (int j = C-1; j >= 0; j--)  {  if (mat[ij] == 1)  isOne = true;  else if (isOne)  res++;  }  }  // Traversing across columns  // for up and down directions.  for (int j = 0; j < C; j++)  {  // 1 is not seen yet  bool isOne = false;   for (int i = 0; i < R; i++)  {  if (mat[ij] == 1)  isOne = true;  else if (isOne)  res++;  }  isOne = false;  for (int i = R-1; i >= 0; i--)  {  if (mat[ij] == 1)  isOne = true;  else if (isOne)  res++;  }  }  return res; } // Driver code to test above methods  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));  } } // This code is contributed by vt_m.

JavaScript

<script>  // Javascript program to get total   // coverage of all zeros in   // a binary matrix    let R = 4;  let C = 4;  // Returns total coverage  // of all zeros in mat[][]  function getTotalCoverageOfMatrix(mat)  {  let res = 0;  // looping for all   // rows of matrix  for (let i = 0; i < R; i++)  {  // 1 is not seen yet  let isOne = false;   // looping in columns from   // left to right direction  // to get left ones  for (let j = 0; j < C; j++)  {  // If one is found  // from left  if (mat[i][j] == 1)  isOne = true;  // If 0 is found and we   // have found a 1 before.  else if (isOne)  res++;  }  // Repeat the above   // process for right   // to left direction.  isOne = false;  for (let j = C - 1; j >= 0; j--)  {  if (mat[i][j] == 1)  isOne = true;  else if (isOne)  res++;  }  }  // Traversing across columns  // for up and down directions.  for (let j = 0; j < C; j++)  {  // 1 is not seen yet  let isOne = false;   for (let i = 0; i < R; i++)  {  if (mat[i][j] == 1)  isOne = true;  else if (isOne)  res++;  }  isOne = false;  for (let i = R - 1; i >= 0; i--)  {  if (mat[i][j] == 1)  isOne = true;  else if (isOne)  res++;  }  }  return res;  }    let mat = [[0 0 0 0]  [1 0 0 1]  [0 1 1 0]  [0 1 0 0]];    document.write(getTotalCoverageOfMatrix(mat)); </script>

산출

시간 복잡도: O(n²)
보조 공간: O(1)

퀴즈 만들기