バイナリ行列内のすべてのゼロの合計カバレッジ

GfG Practice で試してみる ' title=

#practiceLinkDiv { 表示: なし !重要; }

0 と 1 のみを含むバイナリ行列を考えると、行列のすべての 0 の範囲の合計を見つける必要があります。ここで、特定の 0 の範囲は、0 の周囲の左右上下方向の 1 の総数として定義されます。それらは、ある方向の角点までのどこにでも配置できます。

例:

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 バイナリ行列内のすべてのゼロのカバレッジ試してみてください!

あ 簡単な解決策 この問題を解決するには、ゼロの周りの 1 を個別に数えます。つまり、指定された行列のセルごとにループを各方向に 4 回実行します。いずれかのループで 1 が見つかると、ループが中断され、結果が 1 ずつ増加します。

アン 効率的なソリューション 以下を行うことです。

(現在の走査で) 1 がすでに表示されており、現在の要素が 0 である場合、すべての行を左から右に走査し、結果を増分します。
(現在の走査で) 1 がすでに表示されており、現在の要素が 0 である場合、すべての行を右から左に走査し、結果を増分します。
(現在の走査で) 1 がすでに表示されており、現在の要素が 0 である場合、すべての列を上から下に走査し、結果を増分します。
(現在の走査で) 1 がすでに表示されており、現在の要素が 0 である場合、すべての列を下から上に走査し、結果を増分します。

以下のコードでは、ブール変数 isOne が取得されます。これは、現在の走査ですべて 0 について 1 が見つかるとすぐに true になります。その後、反復結果が 1 つだけインクリメントされ、同じ手順が 4 つの方向すべてに適用されて最終的な答えが得られます。走査のたびに 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)

クイズの作成