今回は、C-Filling 3×3 arrayの模範解答であるDFSを解説します。
はじめに模範解答のコードを示しておきます。
C.cpp
#include <iostream>
using namespace std;
int h[3], w[3], a[3][3];
long long ans = 0;
void dfs(int ij) {
int i = ij / 3, j = ij % 3;
if (i == 3) {
ans++;
return;
}
if (i == 2) {
int x = w[j] - a[0][j] - a[1][j];
if (x <= 0) return;
a[i][j] = x, dfs(ij + 1);
} else if (j == 2) {
int x = h[i] - a[i][0] - a[i][1];
if (x <= 0) return;
a[i][j] = x, dfs(ij + 1);
} else {
for (int x = 1; x <= 30; x++) a[i][j] = x, dfs(ij + 1);
}
}
int main() {
for (int i = 0; i < 3; i++) cin >> h[i];
for (int j = 0; j < 3; j++) cin >> w[j];
if (h[0] + h[1] + h[2] != w[0] + w[1] + w[2]) {
cout << 0 << "\n";
return 0;
}
dfs(0);
cout << ans << "\n";
}
このコードは、3x3のマス目に数値を書き込む方法を探索するためにDFS（深さ優先探索）を使用しています。以下に、コードの主要な部分を詳しく解説します。
1. 変数の宣言:
-
h[3], w[3]: 各行と列の合計値を格納する配列。 -
a[3][3]: 3x3のマス目の値を格納する2次元配列。 -
ans: 条件を満たす書き込み方法の数。
2. DFS関数 (void dfs(int ij)):
この関数は、現在のマス目の位置ijを引数として受け取り、そのマス目に数値を書き込む方法を再帰的に探索します。
-
int i = ij / 3, j = ij % 3;:ijを使用して行iと列jを計算します。 -
if (i == 3): すべてのマス目が埋まった場合、答えのカウントを増やします。 -
if (i == 2): 最後の行の場合、列の合計から既に書き込まれている値を引いて、現在のマス目の値を計算します。 -
else if (j == 2): 最後の列の場合、行の合計から既に書き込まれている値を引いて、現在のマス目の値を計算します。 -
else: それ以外の場合、1から30までのすべての値を試して、次のマス目に進みます。
3. メイン関数 (int main()):
- 入力を受け取ります。
-
if (h[0] + h[1] + h[2] != w[0] + w[1] + w[2]): 行と列の合計が等しくない場合、条件を満たす方法は存在しないため、0を出力します。 -
dfs(0): 最初のマス目からDFSを開始します。 - 最後に、答えを出力します。
例:
入力が 3 4 6 3 3 7 の場合、以下のように動作します。
- 行と列の合計が等しいか確認します。
- 最初のマス目からDFSを開始します。
- 各マス目に1から30までの値を試しながら、条件を満たすか確認します。
- すべてのマス目が埋まった場合、答えのカウントを増やします。
- 最終的に、答えとして1が出力されます。
このように、DFSを使用して3x3のマス目に数値を書き込むすべての方法を探索し、条件を満たす方法の数を計算しています。