C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++のバイナリ行列で1によってブロックされているすべての0をカウントします


このチュートリアルでは、バイナリ行列で1によってブロックされている0の数を見つけるプログラムについて説明します。

このために、バイナリマトリックスが提供されます。私たちのタスクは、1によってブロックされているマトリックス内のすべての0を見つけてカウントすることです。

#include <iostream>
using namespace std;
#define Row 4
#define Col 5
int r[4] = { 0, 0, 1, -1 };
int c[4] = { 1, -1, 0, 0 };
bool isSafe(int x, int y, int M[][Col]) {
   if (x >= 0 && x <= Row && y >= 0 &&
      y <= Col && M[x][y] == 0)
      return true;
   return false;
}
//performing DFS in the matrix
void DFS(int x, int y, int M[][Col]) {
   //marking the node as visited
   M[x][y] = 1;
   for (int k = 0; k < 4; k++)
      if (isSafe(x + r[k], y + c[k], M))
         DFS(x + r[k], y + c[k], M);
}
//returning count of blocked 0s
int CountAllZero(int M[][Col]){
   for (int i = 0; i < Col; i++)
      if (M[0][i] == 0)
         DFS(0, i, M);
   for (int i = 0; i < Col; i++)
      if (M[Row - 1][i] == 0)
         DFS(Row - 1, i, M);
   for (int i = 0; i < Row; i++)
      if (M[i][0] == 0)
         DFS(i, 0, M);
   for (int i = 0; i < Row; i++)
      if (M[i][Col - 1] == 0)
         DFS(i, Col - 1, M);
//counting all zeros which are surrounded by 1
int result = 0;
for (int i = 0; i < Row; i++)
   for (int j = 0; j < Col; j++)
      if (M[i][j] == 0)
         result++;
   return result;
}
int main(){
   int M[][Col] = { { 1, 1, 1, 0, 1 },{ 1, 0, 0, 1, 0 },{ 1, 0, 1, 0, 1 },{ 0, 1, 1, 1, 1 } };
   cout << CountAllZero(M) << endl;
   return 0;
}

出力

4

  1. C ++の行列式?

    行列式は、正方行列の場合にのみ、最初の行の補因子に対応する補因子の行列式を掛け、それらに代替の符号を追加して最終結果を得ることができます。 $$ A =\ begin {bmatrix} a&b&c \\ d&e&f \\ g&h&i \\ \ end {bmatrix} | A | =a(ei-fh)-b(di-gf)+ c(dh-eg)$$ 最初に、行列と行列の次元値を取得するdeterminantOfMatrix(int mat [N] [N]、intdimension)関数があります。行列が1次元しかない場合は、[0][0]行列値を返します。この条件は、各再帰呼び出しの次元を減ら

  2. C++でバイナリ行列をゼロ行列に変換する演算の数をカウントするプログラム

    バイナリ行列があるとします。ここで、1つのセルを取得し、そのセルとそのすべての隣接セル(上、下、左、右)を反転する操作について考えてみます。行列に0のみが含まれるように、必要な操作の最小数を見つける必要があります。解決策がない場合は、-1を返します。 したがって、入力が次のような場合 0 0 1 0 その場合、出力は3になります。 これを解決するには、次の手順に従います- サイズの配列ディレクトリを定義します:4 x 2:={{1、0}、{0、1}、{-1、0}、{0、-1}} const int inf =10 ^ 6 関数getP