6

私はプログラミング コンテストの練習をしています。このコンテストでは、問題ごとに 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() )
4

3 に答える 3

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

    }

}
于 2013-06-30T02:59:25.800 に答える