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
- 関数getPos()を定義します。これには、i、j、 が必要です。
- return i * c + j
- 1つの関数getCoord()を定義します。これにはxが必要です
- 1ペアのretを定義する
- ret [0]:=x / c
- ret [1]:=x mod c
- return ret
- メインの方法から次の手順を実行します。
- マスク:=0
- r:=行列の行数
- c:=行列の列数
- 最後:=r * c
- iを初期化する場合:=0、i
- jを初期化する場合:=0、j
- mask:=mask XOR(matrix [i、j] * 2 ^ getPos(i、j))
- mask:=qの最初の要素
- qから要素を削除
- iを初期化する場合:=0、i <が最後の場合、更新(iを1増やします)、次のようにします。
- 1ペアの座標を定義する
- x:=coord [0]
- y:=coord [1]
- nmask:=mask
- nmask:=nmask XOR 2 ^ i
- 初期化k:=0の場合、k <4の場合、更新(kを1増やします)、次のようにします。
- nx:=x + dir [k、0]
- ny:=y + dir [k、1]
- nxとnyが行列の範囲内にない場合、次のようになります。
- 次の部分を無視し、次の反復にスキップします
- pos:=getPos(nx、ny)
- nmask:=nmask XOR(2 ^ pos)
- dist[nmask]が-1またはdist[nmask]>dist [mask] + 1と同じ場合、次のようになります。
- dist [nmask]:=dist [mask] + 1
- nmaskをqに挿入
理解を深めるために、次の実装を見てみましょう-
例
#include using namespace std; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int c; int r; int last; const int inf = 1e6; int getPos(int i, int j){ return i * c + j; } pair getCoord(int x){ pair ret; ret.first = x / c; ret.second = x % c; return ret; } int solve(vector>& matrix) { int mask = 0; r = matrix.size(); c = r ? matrix[0].size() : 0; last = r * c; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ mask ^= (matrix[i][j] << getPos(i, j)); } } vector dist(1 << 9, -1); queue q; q.push(mask); dist[mask] = 0; while(!q.empty()){ mask = q.front(); q.pop(); for(int i = 0; i < last; i++){ pair coord = getCoord(i); int x = coord.first; int y = coord.second; int nmask = mask ; nmask ^= (1 << i); for(int k = 0; k < 4; k++){ int nx = x + dir[k][0]; int ny = y + dir[k][1]; if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue; int pos = getPos(nx, ny); nmask ^= (1 << pos); } if(dist[nmask] == -1 || dist[nmask] > dist[mask] + 1){ dist[nmask] = dist[mask] + 1; q.push(nmask); } } } return dist[0]; } int main(){ vector> v = {{0, 0},{1, 0}}; cout << solve(v); }
入力
{{0, 0},{1, 0}}
出力
3
-
C++で有効な三角形のトリプレットの数を数えるプログラム
数の配列があるとすると、三角形の辺の長さとして取ると、三角形を作ることができる配列から選択されたトリプレットの数を見つける必要があります。したがって、入力が[2,2,3,4]の場合、最初の2を使用する3つのトリプレット[2,3,4]、2番目の2を使用する[2,3,4]があるため、結果は3になります。 [2,2,3]。 これを解決するには、次の手順に従います- ret:=0、n:=numのサイズ、numの並べ替え n −1から0までの範囲のiの場合 右:=i − 1、左:=0 左<右 合計:=nums[左]+nums[右] nums [i]の場合、retを
-
C++でバイナリ行列をゼロ行列に変換するためのフリップの最小数
mxnのバイナリ行列マットがあるとします。 1つのステップで、1つのセルを選択し、そのビットとその4つの隣接セルすべて(存在する場合)を反転できます。マットをゼロ行列に変換するために必要な最小ステップ数を見つける必要があります。解決策がない場合は、-1を返します。 したがって、指定された入力が[[0,0]、[0,1]]のような場合、変更は-のようになります。 したがって、3つのステップが必要で、出力は3になります。 これを解決するには、次の手順に従います- n:=行数、m:=列数、x:=0 iを初期化する場合:=0、i