Jak dopasować segmenty sztuki ASCII do sztuki ASCII?

Question

Ćwiczę na konkursie programistycznym, w którym będę miał wybór dla każdego problemu, czy używać Pythona czy C++, więc jestem otwarty na rozwiązanie w każdym z tych języków - niezależnie od tego, jaki język najlepiej pasuje do tego problemu.

Adres URL poprzedniego problemu, na którym utknąłem, to http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf, problem F ("Mapy").

Zasadniczo polega to na dopasowywaniu zdarzeń małego kawałka sztuki ASCII w obrębie dużego. W C++ mogę utworzyć wektor dla każdego elementu sztuki ASCII. Problem polega na tym, jak dopasować go, gdy mniejszy kawałek jest wieloliniowy.

Nie mam pojęcia, jak sobie z tym poradzić. Nie chcę całego napisanego dla mnie kodu, tylko ideę logiki potrzebnej do rozwiązania problemu.

Dzięki za pomoc.

Oto co mam do tej pory:

#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; 
} 

EDIT: Od komentarzach poniżej Mam rozwiązanie w Pythonie od J.F. Sebastian. Działa, ale nie rozumiem tego wszystkiego. Skomentowałem, co mogłem, ale potrzebuję pomocy w zrozumieniu instrukcji return w funkcji 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) 
) 

Wyrażenie generator mógłby być zapisane w jawnych dla pętli bloków:

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 

Porównanie (pattern == ..) zwraca Prawda/Fałsz, które są równe 1/0 w Pythonie.

Lista zrozumienie, że buduje submatrixes do porównania z wzorem może być zoptymalizowane, aby powrócić wcześniej:

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

lub używając jawne dla pętli bloków:

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

Nie myśl w kategoriach linii. Przeczytaj całą stronę w ciągu znaków i traktuj znaki końca linii jak wszystkie inne.

(Być może, że to tajemnicze wskazówkę, ale pytałem tylko dla „idei”, jak to zrobić).

EDIT: Ponieważ wiesz ogólnych wymiarów obrazu, można policzyć znaki naprzód od pierwszego wiersza wzoru, który próbujesz dopasować, aby dopasować drugi wiersz i tak dalej dla kolejnych linii.

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; 

    } 

}