ACM (UVa) : 10855


// http://online-judge.uva.es/p/v108/10855.html

#include <stdio.h>

char big [102] [102];
char small [102] [102];
int n, N;

void without_rotation ()
{
    int count = 0;

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            if ( big [i] [j] == small [0] [0] ) {
                if ( i + n > N || j + n > N )
                    continue;
                bool flag = true;
                for ( int k = 0; k < n; k++ ) {
                    for ( int l = 0; l < n; l++ ) {
                        if ( small [k] [l] != big [i + k] [j + l] ) {
                            flag = false;
                            k = l = n;
                        }
                    }
                }

                if ( flag )
                count++;
            }
        }
    }

    printf ("%d ", count);

}

void rotation_90 ()
{
    int count = 0;

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            if ( big [i] [j] == small [n - 1] [0] ) {
                if ( i + n > N || j + n > N )
                    continue;
                bool flag = true;
                for ( int k = 0; k < n; k++ ) {
                    for ( int l = 0; l < n; l++ ) {
                        if ( small [n - 1 - l] [k] != big [i + k] [j + l] ) {
                            flag = false;
                            k = l = n;
                        }
                    }
                }

                if ( flag )
                count++;
            }
        }
    }

    printf ("%d ", count);
}

void rotation_180 ()
{
    int count = 0;

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            if ( big [i] [j] == small [n - 1] [n - 1] ) {
                if ( i + n > N || j + n > N )
                    continue;
                bool flag = true;
                for ( int k = 0; k < n; k++ ) {
                    for ( int l = 0; l < n; l++ ) {
                        if ( small [n - 1 - k] [n - 1 - l] != big [i + k] [j + l] ) {
                            flag = false;
                            k = l = n;
                        }
                    }
                }

                if ( flag )
                count++;
            }
        }
    }

    printf ("%d ", count);
}

void rotation_270 ()
{
    int count = 0;

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            if ( big [i] [j] == small [0] [n - 1] ) {
                if ( i + n > N || j + n > N )
                    continue;
                bool flag = true;
                for ( int k = 0; k < n; k++ ) {
                    for ( int l = 0; l < n; l++ ) {
                        if ( small [l] [n - 1 - k] != big [i + k] [j + l] ) {
                            flag = false;
                            k = l = n;
                        }
                    }
                }

                if ( flag )
                count++;
            }
        }
    }

    printf ("%d\n", count);
}

int main ()
{
    while ( scanf ("%d %d", &N, &n) ) {

        if ( !N && !n )
        return 0;

        for ( int i = 0; i < N; i++ )
        scanf ("%s", big [i]);

        for ( int i = 0; i < n; i++ )
        scanf ("%s", small [i]);

        without_rotation ();
        rotation_90 ();
        rotation_180 ();
        rotation_270 ();
    }

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s