我正在为一个编程竞赛练习,在这个竞赛中,我可以选择使用 Python 还是 C++ 来解决每个问题,因此我对任何一种语言的解决方案都持开放态度——无论哪种语言最适合这个问题。
我坚持的过去问题的 URL 是http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf,问题 F(“地图”) .
基本上,它涉及在一个大的 ASCII 艺术中匹配出现的一小块 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
. 它有效,但我不明白这一切。我已经评论了我可以但需要帮助来理解函数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() )