我正在为一个编程竞赛练习，在这个竞赛中我可以选择使用 Python 还是 C++ 来解决每个问题，所以我愿意接受任何一种语言的解决方案——无论哪种语言最适合这个问题。

我遇到的过去问题的 URL 是 http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf , 问题 F(“ map ”)。

基本上，它涉及在一个大的 ASCII 艺术中匹配一小段 ASCII 艺术的出现。在 C++ 中，我可以为每一幅 ASCII 艺术作品制作一个 vector 。问题是当小块是多行时如何匹配。

我不知道该怎么做。我不希望所有代码都为我编写，只希望了解问题所需的逻辑。

感谢您的帮助。

这是我到目前为止所得到的:

#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. 得到了一个 Python 解决方案。塞巴斯蒂安。它有效，但我不明白这一切。我已经评论了我可以但需要帮助理解 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() )

最佳答案

#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 循环 block 重写生成器表达式:

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/False。

构建子矩阵以与模式进行比较的列表推导式可以优化为更早返回:

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

或者使用明确的 for 循环 block :

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

关于c++ - 如何在 ASCII 艺术中匹配 ASCII 艺术片段？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17386458/