[AtCoder]ABC 054B – Template Matching[C++]

AtCoderの過去問をC++で解いていきます。今回は、ABC 054B – Template Matchingだけです。B問題に入ってから、一日に複数問、解くのが難しくなってきました。

ABC 054B – Template Matching

問題

縦N行、横N列に画素が並んだ画像Aと、縦M行、横M列に画素が並んだテンプレート画像Bが与えられます。
画素は画像を構成する最小単位であり、ここでは1×1の正方形とします。
また、与えられる画像は全て2値画像であり、各画素の色は白と黒の2種類で表されます。
入力において、全ての画素は文字で表されており、.は白色の画素、 # は黒色の画素に対応します。
画像AはN個の文字列A1,…,ANで表されます。
文字列Aiのj文字目は、画像Aの上からi番目、左からj番目の画素に対応します。(1≦i,j≦N)
同様に、テンプレート画像BはM個の文字列B1,…,BMで表されます。
文字列Biのj文字目は、テンプレート画像Bの上からi番目、左からj番目の画素に対応します。(1≦i,j≦M)
画像の平行移動のみ許されるとき、テンプレート画像Bが画像Aの中に含まれているかを判定してください。

自分の回答

#include <bits/stdc++.h>
using namespace std;
int main () {
  int N, M;
  cin >> N >> M;
  string A[N],B[M];
  // 入力の受付
  for(int i = 0; i < N; i++){
    cin >> A[i];
  } 
  for(int i = 0; i < M; i++){
    cin >> B[i];
  }
  // bool型の宣言
  bool ans = false;
  // 一行ずつ取り出して、一致しているか判断
  for(int i = 0; i <= N - M; i++){
    for(int j = 0; j <= N - M; j++){
      int cnt = 0;
      for(int k = 0; k < M; k++){
        if(B[k] == A[i + k].substr(j,M)){
          cnt++;
        }
      }
      if(cnt == M) {
        ans = true;
        break;
      }
    }
    if(ans){
      break;
    }
  }
  // 出力
  if(ans){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

難しすぎでは?色々新しい要素が出てきました。
入力を受け付けた後、15行目でbool型で変数ansを宣言しています。真か偽かのみを格納するのなら、bool型が適しています。
次に、for文を使って一行一行取り出してきます。forの範囲をN-Mとしているのは、例えば、画像Aの一番下の行が、2行以上あるテンプレート画像Bと一致しても確かめるまでもなく、一致しないことがわかっているからです。
20行目から始まるfor文で取り出した行内で、substr関数を使って文字列を切り出して、一致しているか確認しています。もし、文字列が一致したら、変数cntの値が増えていきます。もし、cntとテンプレートの行数Mの値が等しければ、テンプレートが完全に一致したことを示すので、ansをtrueとします。

bool型
真か偽の格納のみを目的として変数を作成する際にはbool型が適しています。

substr関数
部分文字列を取得します。
変数.substr(pos,n)という形で使い、pos番目からn要素の文字列を返します。

string s = "abcdefgh";

cout << s.substr(0,2) << endl;  => "ab"
cout << s.substr(2,3) << endl;  => "cde"