如何在ASCII艺术中匹配ASCII艺术片段？

Question

我正在为一个编程竞赛练习，对于每个问题，我都可以选择使用Python或C++，因此我可以使用任何最适合此问题的语言。 我卡在了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;
}

编辑：从下面的评论中，我得到了Python的解决方案，来自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() )

- user1318194

---

作为起点，我建议您将大部分和小部分都定义为2D数组，可能是布尔值，其中“true”表示建筑物，“false”表示雪。然后，您需要使用一些循环技巧在大矩阵中找到每个小矩阵的出现。 - FThompson

@Vulcan 谢谢，看起来应该可以。我会试一下的。也许你可以把它作为答案添加，这样我就可以接受它 :) - user1318194

好的，谢谢。我正在忙着尝试编写它（目前是用C++），并考虑任何建议 :) - user1318194

这是Python的暴力实现。您可以使用它来测试不同的输入。 - jfs

@J.F.Sebastian 好的，那很有效。如果您加上注释会更好，如果您添加答案，我可以接受它。 - user1318194

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

生成器表达式可以使用显式的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

在Python中，比较操作（pattern == ..）返回True/False，它们分别等于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

- jfs

Answer 2

不要按行处理，将整个页面读入字符串并像处理其他字符一样处理换行符。

（你可能认为这是一个神秘的提示，但你只是要求提供“想法”如何做到。）

编辑：由于你知道图片的整体尺寸，你可以从要匹配的模式的第一行向前计算字符，以匹配第二行，以此类推匹配后续行。

- dodgethesteamroller

---

好的，那是一个很好的观点，但是看着我链接到的问题的例子，我不知道它怎么能起作用。换行符确实会被计算在内。抱歉我无法解释清楚，但是看一下例子你可能就明白了。 - user1318194

忽略行尾符号（EOLs）后，输入就失去了二维的意义，这意味着它无法与类似矩阵的输入进行匹配。如果你建议用另一个字符替换行尾符号，并将整个输入视为向量处理，那实际上它已经这样做了，但是行尾符号在以类似矩阵格式显示二维信息时提供了最清晰的表达。 - FThompson

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;

    }

}

- dmi

---

抱歉，我不是指那一个。如果你往下滚动，你会看到问题 F（标题为“地图”）。 - user1318194

谢谢。是的，对我来说也一样，我可以做到，但我不知道如何处理多行模式。 - user1318194