【AtCoder】ABC 430 B - Count Subgrid

2025-11-3

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 141 / NoviSteps: 4Q / 配点: 250 点

問題概要

$N$ 行 $N$ 列からなるグリッドがあり、グリッドの上から $i$ 行目左から $j$ 列目のマスは、 $S_{i,j}$ が#のとき黒く、.のとき白く塗られている。

このグリッドから縦 $M$ 行横 $M$ 列の領域を取り出して得られるマスの塗られ方は何種類あるか求めよ。

制約

$1\leq M \leq N \leq 10$
$N,M$ は整数

考察

種類数だけを求めればよいので、setを用いるのが良いだろう。

グリッドから $M \times M$ の領域を取り出してきたものを、vector<string>などで保存し、setにそのまま突っ込んでいく。

最後にそのsetのサイズを出力すればよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N, M;
11.    cin >> N >> M;
12.    vector<string> S(N);
13.    rep(i, 0, N) cin >> S[i];
14. 
15.    set<vector<string>> st;
16.    rep(i, 0, N - M + 1) rep(j, 0, N - M + 1)
17.    {
18.        vector<string> subgrid(M);
19.        rep(di, 0, M)
20.        {
21.            subgrid[di] = S[i + di].substr(j, M);
22.        }
23.        st.insert(subgrid);
24.    }
25. 
26.    cout << st.size() << endl;
27. 
28.    return 0;
29.}