ПЕТИ МЕЖДУУНИВЕРСИТЕТСКИ ТУРНИР ПО ПРОГРАМИРАНЕ
БСУ, Бургас, 19 май 2002 г.
    Задача G. Картина
    При работа с двумерни растерни изображения (картини) се срещат разнообразни проблеми. Един от тях е да се види дали някоя малка картина се намира в дадена голяма картина. За по-голямо удобство ще разглеждаме само правоъгълни картини и ще изискваме по-малката картина да се среща точно, т.е. не се допускат разлики в малък брой точки (пиксели), както е при реалните проблеми.
    Една картина с размери PxQ се състои от P.Q точки, всяка в един от 255 възможни цвята. Може да разглеждаме картината като матрица с Q реда и P стълба, а всеки елемент на матрицата като цяло число между 1 и 255 – цветът на съответната точка от картината. На фиг. 1 можете да видите една примерна картина 5x7.
    Вашата задача е да намерите колко пъти една по-малка картина с размери AxB (0<A<151, 0<B<151) се среща в друга по-голяма картина с размери CxD (0<C<1501, 0<D<1501). Срещанията на по-малката картина могат евентуално да се припокриват.
 
10
56
30
32
255
11
30
32
31
255
11
32
31
123
201
48
47
1
1
67
49
50
5
5
67
111
111
66
30
32
222
222
66
32
31

Фиг.1 – картина 5x7
30
32
32
31

Фиг.2 – картина 2x2

Картината на фиг. 2 с размери 2x2 се среща точно 3 пъти в картината на фиг. 1. Клетките от фиг. 1, които съответстват на клетките (1 1), (1 2), (2 1) и (2 2) от фиг. 2, са:

    Забележете, че по-горе елементите на матриците са зададени с двойка числа: ред и стълб на съответния елемент.

    Име на входния файл: PIC.INP. Описание на входния файл:
    Входният файл съдържа различни групи малка и голяма картина. Описанието на всяка група започва с един ред съдържащ четири числа разделени с интервал: A, B, C и D (A <= C и B <= D). Всеки от следващите B реда съдържа по A числа разделени с интервал – елементите на поредния ред от матрицата, съответстваща на малката картина. Всеки от следващите D реда съдържа по C числа разделени с интервал – елементите на поредния ред от матрицата съответстваща на голямата картина. Описанията на всяка група следват едно след друго във входния файл. Входният файл завършва с един ред, на който има четири нули разделени с интервал – 0 0 0 0.

    Име на изходния файл: PIC.OUT. Описание на изходния файл:
Изходният файл трябва да съдържа по един ред за всяка група, като на този ред трябва да е записано колко пъти по-малката картина се среща в по-голямата картина за съответната група. Последователността на редовете в изходния файл трябва да съответства на последователността на групите от входния файл.

Примерен входен файл:
2 2 5 7
30 32
32 31
10 56 30 32 255
11 30 32 31 255
11 32 31 123 201
48 47 1 1 67
49 50 5 5 67
111 111 66 30 32
222 222 66 32 31
2 2 3 3
10 10
10 10
10 10 10
10 10 10
10 10 10
0 0 0 0 		Изходен файл за примерния входен файл:
3
4