バイナリ行列の水平および垂直の対称性を確認する

次の 2D バイナリ行列が与えられると、 N 行と M 列。タスクは、行列が水平対称であるか、垂直対称であるか、またはその両方であるかを確認することです。最初の行が最後の行と同じ、2 番目の行が最後から 2 番目の行と同じ、などの場合、行列は水平対称であると言われます。また、最初の列が最後の列と同じ、2 番目の列が最後から 2 番目の列と同じ、などの場合、行列は垂直対称であると言われます。

印刷' 垂直 ' 行列が垂直対称の場合 ' 水平方向 ' 行列が垂直対称の場合 ' 両方 ' マトリックスが垂直および水平対称の場合、および ' いいえ ' 対称でない場合。

例:

データ構造

入力： N = 3 M = 3
0 1 0
0 0 0
0 1 0
出力： 両方
説明： 1列目と3列目は同じで、2列目も真ん中です。つまり左右対称。同様に、1列目と3列目は同じで、2列目も中央にあるので垂直対称です。

入力： N = 3 M = 3
0 0 1
1 1 0
0 0 1
出力： 両方

アプローチ： このアイデアは、2 つの行 (または列) を示すポインターを使用し、指定された両方の行 (または列) の各セルを比較することです。

ジャワポイント

水平対称の場合、1 つのポインター i = 0 と別のポインター j = N - 1 を初期化します。
次に、i 行目と j 行目の各要素を比較します。各ループサイクルで i を 1 ずつ増やし、j を 1 ずつ減らします。
- 同一ではない要素が少なくとも 1 つ見つかった場合は、行列を水平対称ではないとしてマークします。
同様に、垂直対称の場合は、1 つのポインター i = 0 と別のポインター j = M - 1 を初期化します。
ここで、i 列目と j 列目の各要素を比較します。各ループサイクルで i を 1 ずつ増やし、j を 1 ずつ減らします。
- 同一でない要素が少なくとも 1 つ見つかった場合は、行列を垂直対称でないとマークします。

以下は上記のアイデアの実装です。

C++

// C++ program to find if a matrix is symmetric. #include    #define MAX 1000 using namespace std; void checkHV(int arr[][MAX] int N int M) {  // Initializing as both horizontal and vertical  // symmetric.  bool horizontal = true vertical = true;  // Checking for Horizontal Symmetry. We compare  // first row with last row second row with second  // last row and so on.  for (int i = 0 k = N - 1; i < N / 2; i++ k--) {  // Checking each cell of a column.  for (int j = 0; j < M; j++) {  // check if every cell is identical  if (arr[i][j] != arr[k][j]) {  horizontal = false;  break;  }  }  }  // Checking for Vertical Symmetry. We compare  // first column with last column second column  // with second last column and so on.  for (int j = 0 k = M - 1; j < M / 2; j++ k--) {  // Checking each cell of a row.  for (int i = 0; i < N; i++) {  // check if every cell is identical  if (arr[i][j] != arr[i][k]) {  vertical = false;  break;  }  }  }  if (!horizontal && !vertical)  cout << 'NOn';  else if (horizontal && !vertical)  cout << 'HORIZONTALn';  else if (vertical && !horizontal)  cout << 'VERTICALn';  else  cout << 'BOTHn'; } // Driven Program int main() {  int mat[MAX][MAX]  = { { 0 1 0 } { 0 0 0 } { 0 1 0 } };  checkHV(mat 3 3);  return 0; }

Java

// Java program to find if // a matrix is symmetric. import java.io.*; public class GFG {  static void checkHV(int[][] arr int N int M)  {  // Initializing as both horizontal  // and vertical symmetric.  boolean horizontal = true;  boolean vertical = true;  // Checking for Horizontal Symmetry.  // We compare first row with last  // row second row with second  // last row and so on.  for (int i = 0 k = N - 1; i < N / 2; i++ k--) {  // Checking each cell of a column.  for (int j = 0; j < M; j++) {  // check if every cell is identical  if (arr[i][j] != arr[k][j]) {  horizontal = false;  break;  }  }  }  // Checking for Vertical Symmetry. We compare  // first column with last column second column  // with second last column and so on.  for (int j = 0 k = M - 1; j < M / 2; j++ k--) {  // Checking each cell of a row.  for (int i = 0; i < N; i++) {  // check if every cell is identical  if (arr[i][j] != arr[i][k]) {  horizontal = false;  break;  }  }  }  if (!horizontal && !vertical)  System.out.println('NO');  else if (horizontal && !vertical)  System.out.println('HORIZONTAL');  else if (vertical && !horizontal)  System.out.println('VERTICAL');  else  System.out.println('BOTH');  }  // Driver Code  static public void main(String[] args)  {  int[][] mat  = { { 1 0 1 } { 0 0 0 } { 1 0 1 } };  checkHV(mat 3 3);  } } // This code is contributed by vt_m.

Python3

# Python3 program to find if a matrix is symmetric. MAX = 1000 def checkHV(arr N M): # Initializing as both horizontal and vertical # symmetric. horizontal = True vertical = True # Checking for Horizontal Symmetry. We compare # first row with last row second row with second # last row and so on. i = 0 k = N - 1 while(i < N // 2): # Checking each cell of a column. for j in range(M): # check if every cell is identical if (arr[i][j] != arr[k][j]): horizontal = False break i += 1 k -= 1 # Checking for Vertical Symmetry. We compare # first column with last column second column # with second last column and so on. i = 0 k = M - 1 while(j < M // 2): # Checking each cell of a row. for i in range(N): # check if every cell is identical if (arr[i][j] != arr[i][k]): vertical = False break j += 1 k -= 1 if (not horizontal and not vertical): print('NO') elif (horizontal and not vertical): print('HORIZONTAL') elif (vertical and not horizontal): print('VERTICAL') else: print('BOTH') # Driver code mat = [[1 0 1] [0 0 0] [1 0 1]] checkHV(mat 3 3) # This code is contributed by shubhamsingh10

// C# program to find if // a matrix is symmetric. using System; public class GFG {  static void checkHV(int[ ] arr int N int M)  {  // Initializing as both horizontal  // and vertical symmetric.  bool horizontal = true;  bool vertical = true;  // Checking for Horizontal Symmetry.  // We compare first row with last  // row second row with second  // last row and so on.  for (int j = 0 k = N - 1; j < N / 2; j++ k--) {  // Checking each cell of a column.  for (int i = 0; i < M; i++) {  // check if every cell is identical  if (arr[i j] != arr[i k]) {  horizontal = false;  break;  }  }  }  // Checking for Vertical Symmetry. We compare  // first column with last column second column  // with second last column and so on.  for (int i = 0 k = M - 1; i < M / 2; i++ k--) {  // Checking each cell of a row.  for (int j = 0; j < N; j++) {  // check if every cell is identical  if (arr[i j] != arr[k j]) {  horizontal = false;  break;  }  }  }  if (!horizontal && !vertical)  Console.WriteLine('NO');  else if (horizontal && !vertical)  Console.WriteLine('HORIZONTAL');  else if (vertical && !horizontal)  Console.WriteLine('VERTICAL');  else  Console.WriteLine('BOTH');  }  // Driver Code  static public void Main()  {  int[ ] mat  = { { 1 0 1 } { 0 0 0 } { 1 0 1 } };  checkHV(mat 3 3);  } } // This code is contributed by vt_m.

PHP

 // PHP program to find if  // a matrix is symmetric. function checkHV($arr $N $M) { // Initializing as both horizontal  // and vertical symmetric. $horizontal = true; $vertical = true; // Checking for Horizontal Symmetry.  // We compare first row with last row // second row with second last row  // and so on. for ($i = 0 $k = $N - 1; $i < $N / 2; $i++ $k--) { // Checking each cell of a column. for ($j = 0; $j < $M; $j++) { // check if every cell is identical if ($arr[$i][$j] != $arr[$k][$j]) { $horizontal = false; break; } } } // Checking for Vertical Symmetry.  // We compare first column with  // last column second column with  // second last column and so on. for ($j = 0 $k = $M - 1; $j < $M / 2; $j++ $k--) { // Checking each cell of a row. for ($i = 0; $i < $N; $i++) { // check if every cell is identical if ($arr[$i][$j] != $arr[$i][$k]) { $horizontal = false; break; } } } if (!$horizontal && !$vertical) echo 'NOn'; else if ($horizontal && !$vertical) cout << 'HORIZONTALn'; else if ($vertical && !$horizontal) echo 'VERTICALn'; else echo 'BOTHn'; } // Driver Code $mat = array(array (1 0 1) array (0 0 0) array (1 0 1)); checkHV($mat 3 3); // This code is contributed by nitin mittal.  ?>

JavaScript

<script>  // Javascript program to find if  // a matrix is symmetric.    function checkHV(arr N M)  {    // Initializing as both horizontal  // and vertical symmetric.  let horizontal = true;  let vertical = true;    // Checking for Horizontal Symmetry.  // We compare first row with last  // row second row with second  // last row and so on.  for (let i = 0 k = N - 1;  i < parseInt(N / 2 10); i++ k--) {    // Checking each cell of a column.  for (let j = 0; j < M; j++) {  // check if every cell is identical  if (arr[i][j] != arr[k][j]) {  horizontal = false;  break;  }  }  }    // Checking for Vertical Symmetry. We compare  // first column with last column second column  // with second last column and so on.  for (let j = 0 k = M - 1;  j < parseInt(M / 2 10); j++ k--) {    // Checking each cell of a row.  for (let i = 0; i < N; i++) {  // check if every cell is identical  if (arr[i][j] != arr[i][k]) {  horizontal = false;  break;  }  }  }    if (!horizontal && !vertical)  document.write('NO');    else if (horizontal && !vertical)  document.write('HORIZONTAL');    else if (vertical && !horizontal)  document.write('VERTICAL');    else  document.write('BOTH');  }    let mat = [ [ 1 0 1 ]  [ 0 0 0 ]  [ 1 0 1 ] ];    checkHV(mat 3 3);   </script>

出力

BOTH

時間計算量: O(N*M)。
補助スペース: ○(1)

二分探索のアルゴリズム

クイズの作成