ASCIIアート内のASCIIアートセグメントのマッチング方法は？

Question

私はPythonまたはC++を使用するかどうかにかかわらず、それぞれの問題に対して選択肢があるプログラミング競争のために練習しています。したがって、どちらの言語でもこの問題に最も適した解決策を見つけることができます。

私が直面している過去の問題のURLはhttp://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf、問題F（「マップ」）です。

基本的には、大きなアートワークの中で小さなアスキーアートの出現と一致します。 C++では、ASCIIアートの各部分にベクトルを作ることができます。問題は、小さい方のピースが複数行の場合にどのようにマッチさせるかです。

私はそれについてどう考えてもわかりません。私はすべてのコードが私のために書かれたのではなく、問題に必要な論理のアイデアだけを望んでいます。

ありがとうございました。

は、ここで私はこれまで持っているものです：

#include <cstdlib> 
#include <iostream> 
#include <string> 
#include <algorithm> 
#include <vector> 

using namespace std; 

int main(int argc, char** argv) 
{ 
    int nScenarios, areaWidth, areaHeight, patternWidth, patternHeight; 

    cin >> nScenarios; 

    for(int a = 0; a < nScenarios; a++) 
    { 
     //get the pattern info and make a vector 
     cin >> patternHeight >> patternWidth; 
     vector< vector<bool> > patternIsBuilding(patternHeight, vector<bool>(patternWidth, false)); 

     //populate data 
     for(int i = 0; i < patternHeight; i++) 
     { 
      string temp; 
      cin >> temp; 
      for(int j = 0; j < patternWidth; j++) 
      { 
       patternIsBuilding.at(i).at(j) = (temp[ j ] == 'X'); 
      } 
     } 

     //get the area info and make a vector 
     cin >> areaHeight >> areaWidth; 
     vector< vector<bool> > areaIsBuilding(areaHeight, vector<bool>(areaWidth, false)); 

     //populate data 
     for(int i = 0; i < areaHeight; i++) 
     { 
      string temp; 
      cin >> temp; 
      for(int j = 0; j < areaWidth; j++) 
      { 
       areaIsBuilding.at(i).at(j) = (temp[ j ] == 'X'); 
      } 
     } 


     //now the vectors contain a `true` for a building and a `false` for snow 
     //need to find the matches for patternIsBuilding inside areaIsBuilding 
     //how? 

    } 


    return 0; 
} 

編集：私はJ.F. SebastianからPythonで解決策を持っている以下のコメントから。それは動作しますが、私はそれをすべて理解していません。私は何ができるのかをコメントしましたが、の文をcount_pattern関数で理解するのに役立つ必要があります。

#function to read a matrix from stdin 
def read_matrix(): 

    #get the width and height for this matrix 
    nrows, ncols = map(int, raw_input().split()) 

    #get the matrix from input 
    matrix = [ raw_input() for _ in xrange(nrows) ] 

    #make sure that it all matches up 
    assert all(len(row) == ncols for row in matrix) 

    #return the matrix 
    return matrix 

#perform the check, given the pattern and area map 
def count_pattern(pattern, area): 

    #get the number of rows, and the number of columns in the first row (cause it's the same for all of them) 
    nrows = len(pattern) 
    ncols = len(pattern[0]) 

    #how does this work? 
    return sum(
     pattern == [ row[ j:j + ncols ] for row in area[ i:i + nrows ] ] 
     for i in xrange(len(area) - nrows + 1) 
     for j in xrange(len(area[i]) - ncols + 1) 
    ) 

#get a number of scenarios, and that many times, operate on the two inputted matrices, pattern and area 
for _ in xrange(int(raw_input())): 
    print count_pattern(read_matrix(), read_matrix()) 

Answer 1

#how does this work? 
return sum(
    pattern == [ row[ j:j + ncols ] for row in area[ i:i + nrows ] ] 
    for i in xrange(len(area) - nrows + 1) 
    for j in xrange(len(area[i]) - ncols + 1) 
) 

ジェネレータ発現が明示forループのブロックを使用して書き直すことができる：

count = 0 
for i in xrange(len(area) - nrows + 1): 
    for j in xrange(len(area[i]) - ncols + 1): 
     count += (pattern == [ row[ j:j + ncols ] 
           for row in area[ i:i + nrows ] ]) 
return count 

比較（pattern == ..）Pythonで1/0に等しいという誤っ/ Trueを返します。

パターンと比較する部分行列を構築し、リスト内包表記が早く返すように最適化することができます。

count += all(pattern_row == row[j:j + ncols] 
      for pattern_row, row in zip(pattern, area[i:i + nrows])) 

または明示的なforループのブロックを使用して：

for pattern_row, row in zip(pattern, area[i:i + nrows]): 
    if pattern_row != row[j:j + ncols]: 
     break # no match (the count stays the same) 
else: # matched (no break) 
    count += 1 # all rows are equal 

Answer 2

行に関しては考えないでください。ページ全体を文字列に読み込み、行末の文字を他の文字と同様に扱います。

（あなたはこれが不可解なヒントだと思うかもしれないが、あなたはどのようにそれを行うには、単に「アイデア」を求めるんでした。）

EDIT：あなたは絵の全体的な寸法を知っているので、あなたは文字を数えることができます2行目と一致させるために一致させようとしているパターンの最初の行から前方に移動し、後続の行にも一致させます。

Answer 3

#include <iostream> 
#include <vector> 

using namespace std; 

int main(){ 

    int numOfRounds; 
    cin >> numOfRounds; 



    for(int round = 0; round < numOfRounds; round++){ 

     int out = 0; 

     int linesToMatch; 
     cin >> linesToMatch; 

     int sizeToMatch; 
     cin >> sizeToMatch; 

     vector <string> v; 
     string t; 

     for (int i = 0; i < linesToMatch; i++){ 
      cin >> t; 
      v.push_back(t); 
     } 

     string s = ""; 

     int rows; 
     cin >> rows; 

     int columns; 
     cin >> columns; 

     for (int j = 0; j < rows; j++){  //map->string 
      cin >> t; 
      s += t; 
     } 

     // main part of implementation 
     // it's mainly basic algebra and index tracking 
     for (int m = 0; m <= rows - linesToMatch; m++){ 
      for (int n = 0; n <= columns - sizeToMatch; n++){ 
       int x; 
       for (x = 0; x < linesToMatch; x++){ 
        int index = (m + x) * columns + n; 
        string newTemp(s.begin() + index, s.begin() + index + sizeToMatch); 
        if (newTemp != v.at(x)) break; 
       } 
       if (x == linesToMatch) out++; 
      } 
     } 

     cout << out << endl; 

    } 

}