如何在ASCII-art中匹配ASCII-art段？

Question

我正在练习一个编程竞赛，在这个竞赛中，我会选择每一个问题，不管是使用Python还是C++，所以我对任何一种语言都有一个解决方案——无论什么语言最适合这个问题。在

我遇到的过去问题的URL是http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf，问题F（“Maps”）。在

基本上，它涉及到在一个大的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得到了一个用Python编写的解决方案。这很管用，但我并不完全明白。{{cd2>在函数中注释了什么。在

^{pr2}$

Answer 1

不要用线条来思考。将整个页面读入字符串，并像对待其他字符一样处理行尾字符。在

（你可能认为这是一个隐晦的暗示，但你只是问了一个如何做的“主意”。）

编辑：因为你知道图片的整体尺寸，所以你可以从你想要匹配的图案的第一行向前数数字符，以便与第二行相匹配，以此类推。在

Answer 2

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

^{pr2}$

比较（pattern == ..）返回True/False，在Python中等于1/0。在

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

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

或使用显式for循环块：

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

    }

}