ASCII 아트 내에서 ASCII 아트 세그먼트를 일치시키는 방법은 무엇입니까?

Question

나는 각 문제에 대해 파이썬이나 C++ 중 어떤 것을 사용할지에 대한 선택의 여지가있는 프로그래밍 경쟁을 위해 연습하고 있으므로 어느 언어로든이 문제에 가장 적합한 솔루션으로 공개됩니다.

내가 붙어있는 지난 문제의 URL은 http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf, 문제 F ("지도")입니다.

기본적으로 큰 아트 내에서 작은 ASCII 아트 조각이 일치하는 것을 포함합니다. 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에서 파이썬의 솔루션을 가지고 아래의 설명에서. 그것은 작동하지만 나는 그것을 모두 이해하지 못합니다. 내가 할 수있는 말은했지만 count_pattern 함수에서 return 문을 이해하는 데 도움이 필요합니다.

#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) 
) 

발전기 표현이 명시위한 루프 블록을 사용하여 다시 작성할 수 있습니다 :

는

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 == ..는)/진정한 파이썬의 1/0에 동일한 것을 False를 반환합니다. 패턴과 비교 submatrixes를 구축

목록의 이해는 이전에 반환하도록 최적화 할 수 있습니다

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

또는 사용하여 명시위한 루프 블록 : 시작점으로

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

줄의 관점에서 생각하지 마십시오. 전체 페이지를 문자열로 읽은 다음 줄의 끝 문자를 다른 문자열과 같이 처리하십시오.

(당신이이 비밀 힌트 생각하지만, 어떻게 그것을 할 그냥 "아이디어"를 요청했다.)

편집 : 당신이 사진의 전체 크기를 알고 있기 때문에, 당신은 문자를 셀 수 두 번째 줄과 일치시키기 위해 일치시키려는 패턴의 첫 번째 줄부터 앞으로 이어지는 줄 등등.

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; 

    } 

}