ABC 054 B - Template Matching
問題概要
“#"と”.“からなる画像(文字列や何本か)が2つ, A, Bとして与えられる. Bの画像がAの画像の中に含まれるかどうかを調べる.
解法
BがAに含まれるかを単純に調べた. Bの左上がAのどこにあるかですべて試して, 一致するものがあるかを調べた.
下記の実装であれば, 変数y, xがBの座標(0,0)をAの(y,x)において調べていることになる.
O(nnmm)なのかな?
ミス
画像処理で一回こういうの書いたことあった.
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; int n, m; string a[55], b[55]; int main(void){ cin >> n >> m; rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; if(n < m){ printf("No\n"); return 0; }else{ rep(y, n - m + 1)rep(x, n - m + 1){ bool flag = true; rep(i, m){ rep(j, m){ if(a[i + y][j + x] != b[i][j]){ flag = false; break; } } if(!flag) break; } if(flag){ printf("Yes\n"); return 0; } } } printf("No\n"); return 0; }