Как сопоставить сегменты искусства ASCII с искусством ASCII?

Question

Как сопоставить сегменты искусства ASCII с искусством ASCII?

Я тренируюсь на соревновании по программированию, в котором у меня будет выбор для каждой проблемы, использовать ли Python или 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;
}

РЕДАКТИРОВАТЬ: Из комментариев ниже, я получил решение в Python от J.F. Sebastian, Это работает, но я не все понимаю. Я прокомментировал, что я мог, но нужна помощь в понимании return заявление в 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() )

6

ascii-art c++python

Решение

Другие решения

Не думай с точки зрения линий. Прочитайте всю страницу в строку и обработайте символы конца строки, как и любой другой.

(Вы можете подумать, что это загадочный намек, но вы просили просто «идею», как это сделать.)

РЕДАКТИРОВАТЬ: так как вы знаете общие размеры изображения, вы можете считать символы вперед от первой строки шаблона, который вы пытаетесь сопоставить, чтобы соответствовать второй строке, и так далее для последующих строк.

1

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

}

}

0

Источник

Accepted Answer

#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 == ..) возвращает True / False, равные 1/0 в Python.

Понимание списка, которое строит подматрицы для сравнения с шаблоном, может быть оптимизировано для возврата раньше:

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

Или используя явные блоки for-loop:

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

1