시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 748 203 93 28.882%

문제

재혁이는 화가인데 거지다. 그래서 새 그림을 그릴 화판조차도 없다. 그러나 재혁이는 방금 유레카를 외쳤다. "아직 팔리지 않은 그림들을 꿰매 이어붙여서 새로운 큰 그림을 만들면 화판도 필요없고 새 그림도 만들고 개이득이다. 이거 완전 빅 픽쳐 아님?" 꼬박 하루의 노동을 거쳐, 재혁이는 큰 그림 걸작 하나를 만들어내고야 말았다.

그러던 어느 날, 재혁이는 예상치 못한 전화를 받고 말았다. 전화의 내용은 아직 팔리지 않았던 그림 중 하나를 사겠다는 것이었다. 그런데 재혁이는 큰 그림을 만드는 데 어떤 그림들을 사용했는지 기록하는 것을 까먹었다. 그래서 자기 걸작의 어느 곳에 그 그림이 사용되었는지를 찾아야 한다.

흑백으로 표현된 그림과 그걸 사용해 만든 걸작이 주어졌을 때, 재혁이가 그림을 찾는 것을 도울 수 있는가? 

입력

첫 번째 줄에 4개의 정수 hp wp hm wm가 주어진다. 각각 사용한 그림의 높이와 너비, 걸작의 높이와 너비를 의미한다. 이어서 hp개의 줄에 걸쳐 사용한 그림이 주어지고, hm개의 줄에 걸쳐 걸작이 주어진다. 그림은 'x' 또는 'o'만으로 이루어져 있다.

각 그림의 너비와 높이는 1 이상 2000 이하이며, 걸작의 넓이와 높이는 각각 사용한 그림의 너비와 높이보다 크거나 같다.

출력

사용한 그림이 걸작에서 있을 수 있는 위치의 개수를 출력한다.

예제 입력 1

4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo

예제 출력 1

4

힌트

W3sicHJvYmxlbV9pZCI6IjEwNTM4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZTQ1IFx1ZDUzZFx1Y2NkMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjN2FjXHVkNjAxXHVjNzc0XHViMjk0IFx1ZDY1NFx1YWMwMFx1Yzc3OFx1YjM3MCBcdWFjNzBcdWM5YzBcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWMwYzggXHVhZGY4XHViOWJjXHVjNzQ0IFx1YWRmOFx1YjliNCBcdWQ2NTRcdWQzMTBcdWM4NzBcdWNjMjhcdWIzYzQgXHVjNWM2XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVjN2FjXHVkNjAxXHVjNzc0XHViMjk0IFx1YmMyOVx1YWUwOCBcdWM3MjBcdWI4MDhcdWNlNzRcdWI5N2MgXHVjNjc4XHVjY2U0XHViMmU0LiAmcXVvdDtcdWM1NDRcdWM5YzEgXHVkMzE0XHViOWFjXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFkZjhcdWI5YmNcdWI0ZTRcdWM3NDQgXHVhZmYwXHViOWU0IFx1Yzc3NFx1YzViNFx1YmQ5OVx1YzVlY1x1YzExYyBcdWMwYzhcdWI4NWNcdWM2YjQgXHVkMDcwIFx1YWRmOFx1YjliY1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWJhNzQgXHVkNjU0XHVkMzEwXHViM2M0IFx1ZDU0NFx1YzY5NFx1YzVjNlx1YWNlMCBcdWMwYzggXHVhZGY4XHViOWJjXHViM2M0IFx1YjljY1x1YjRlNFx1YWNlMCZuYnNwO1x1YWMxY1x1Yzc3NFx1YjRkZFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVhYzcwIFx1YzY0NFx1YzgwNCBcdWJlNDUgXHVkNTNkXHVjY2QwIFx1YzU0NFx1YjJkOD8mcXVvdDsgXHVhZjJjXHViYzE1IFx1ZDU1OFx1YjhlOFx1Yzc1OCBcdWIxNzhcdWIzZDlcdWM3NDQgXHVhYzcwXHVjY2QwLCBcdWM3YWNcdWQ2MDFcdWM3NzRcdWIyOTQmbmJzcDtcdWQwNzAgXHVhZGY4XHViOWJjIFx1YWM3OFx1Yzc5MSZuYnNwO1x1ZDU1OFx1YjA5OFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWIwYjRcdWFjZTBcdWM1N2MgXHViOWQwXHVjNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWIzNTggXHVjNWI0XHViMjkwIFx1YjBhMCwgXHVjN2FjXHVkNjAxXHVjNzc0XHViMjk0IFx1YzYwOFx1YzBjMVx1Y2U1OCBcdWJhYmJcdWQ1NWMgXHVjODA0XHVkNjU0XHViOTdjJm5ic3A7XHViYzFiXHVhY2UwIFx1YjlkMFx1YzU1OFx1YjJlNC4mbmJzcDtcdWM4MDRcdWQ2NTRcdWM3NTggXHViMGI0XHVjNmE5XHVjNzQwJm5ic3A7XHVjNTQ0XHVjOWMxIFx1ZDMxNFx1YjlhY1x1YzljMCBcdWM1NGFcdWM1NThcdWIzNTggXHVhZGY4XHViOWJjIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMGFjXHVhY2EwXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YzVjOFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YzdhY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVhZGY4XHViOWJjXHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWIzNzAgXHVjNWI0XHViNWE0IFx1YWRmOFx1YjliY1x1YjRlNFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1ODhcdWIyOTRcdWM5YzAgXHVhZTMwXHViODVkXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWFlNGNcdWJhMzlcdWM1YzhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWM3OTBcdWFlMzAgXHVhYzc4XHVjNzkxXHVjNzU4IFx1YzViNFx1YjI5MCBcdWFjZjNcdWM1ZDAgXHVhZGY4IFx1YWRmOFx1YjliY1x1Yzc3NCBcdWMwYWNcdWM2YTlcdWI0MThcdWM1YzhcdWIyOTRcdWM5YzBcdWI5N2MmbmJzcDtcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ3NTFcdWJjMzFcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFkZjhcdWFjNzggXHVjMGFjXHVjNmE5XHVkNTc0IFx1YjljY1x1YjRlMCBcdWFjNzhcdWM3OTFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywmbmJzcDtcdWM3YWNcdWQ2MDFcdWM3NzRcdWFjMDAgXHVhZGY4XHViOWJjXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWFjODNcdWM3NDQmbmJzcDtcdWIzYzRcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YWMwMD8mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIDRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IGg8c3ViPnA8XC9zdWI+Jm5ic3A7dzxzdWI+cDxcL3N1Yj4mbmJzcDtoPHN1Yj5tPFwvc3ViPiZuYnNwO3c8c3ViPm08XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFkZjhcdWI5YmNcdWM3NTggXHViMTkyXHVjNzc0XHVjNjQwIFx1YjEwOFx1YmU0NCwgXHVhYzc4XHVjNzkxXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWIxMDhcdWJlNDRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgaDxzdWI+cDxcL3N1Yj5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVhZGY4XHViOWJjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgaDxzdWI+bTxcL3N1Yj5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjNzhcdWM3OTFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YmNcdWM3NDAgJiMzOTt4JiMzOTsgXHViNjEwXHViMjk0ICYjMzk7byYjMzk7XHViOWNjXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFkZjhcdWI5YmNcdWM3NTggXHViMTA4XHViZTQ0XHVjNjQwIFx1YjE5Mlx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSAyMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YmE3MCwgXHVhYzc4XHVjNzkxXHVjNzU4IFx1YjExM1x1Yzc3NFx1YzY0MCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFkZjhcdWI5YmNcdWM3NTggXHViMTA4XHViZTQ0XHVjNjQwIFx1YjE5Mlx1Yzc3NFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFkZjhcdWI5YmNcdWM3NzQgXHVhYzc4XHVjNzkxXHVjNWQwXHVjMTFjIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9wYWludGluZy5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjRweDsgd2lkdGg6MTIxcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwNTM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEJpZyBQYWludGluZyIsImRlc2NyaXB0aW9uIjoiPHA+U2FtdWVsIFcuIEUuIFIuIENyYWZ0IGlzIGFuIGFydGlzdCB3aXRoIGEgZ3Jvd2luZyByZXB1dGF0aW9uLiBVbmZvcnR1bmF0ZWx5LCB0aGUgcGFpbnRpbmdzIGhlIHNlbGxzIGRvIG5vdCBwcm92aWRlIGhpbSBlbm91Z2ggbW9uZXkgZm9yIGhpcyBkYWlseSBleHBlbnNlcyBwbHVzIHRoZSBuZXcgc3VwcGxpZXMgaGUgbmVlZHMuIEhlIGhhZCBhIGJyaWxsaWFudCBpZGVhIHllc3RlcmRheSB3aGVuIGhlIHJhbiBvdXQgb2YgYmxhbmsgY2FudmFzOiAmcXVvdDtXaHkgZG9uJnJzcXVvO3QgSSBjcmVhdGUgYSBnaWdhbnRpYyBuZXcgcGFpbnRpbmcsIG1hZGUgb2YgYWxsIHRoZSB1bnNlbGxhYmxlIHBhaW50aW5ncyBJIGhhdmUsIHN0aXRjaGVkIHRvZ2V0aGVyPyZxdW90Oy4gQWZ0ZXIgYSBmdWxsIGRheSBvZiB3b3JrLCBoaXMgbWFzdGVycGllY2Ugd2FzIGNvbXBsZXRlLjxcL3A+XHJcblxyXG48cD5UaGF0JnJzcXVvO3Mgd2hlbiBoZSByZWNlaXZlZCBhbiB1bmV4cGVjdGVkIHBob25lIGNhbGw6IGEgY2xpZW50IHNhdyBhIHBob3RvZ3JhcGggb2Ygb25lIG9mIGhpcyBwYWludGluZ3MgYW5kIGlzIHdpbGxpbmcgdG8gYnV5IGl0IG5vdyEgSGUgaGFkIGZvcmdvdHRlbiB0byB0ZWxsIHRoZSBhcnQgZ2FsbGVyeSB0byByZW1vdmUgaGlzIG9sZCB3b3JrcyBmcm9tIHRoZSBjYXRhbG9nISBIZSB3b3VsZCB1c3VhbGx5IHdlbGNvbWUgYSBjYWxsIGxpa2UgdGhpcywgYnV0IGhvdyBpcyBoZSBnb2luZyB0byBmaW5kIGhpcyBvbGQgd29yayBpbiB0aGUgaHVnZSBmaWd1cmUgaW4gZnJvbnQgb2YgaGltPzxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGJsYWNrLWFuZC13aGl0ZSByZXByZXNlbnRhdGlvbiBvZiBoaXMgb3JpZ2luYWwgcGFpbnRpbmcgYW5kIGEgYmxhY2stYW5kLXdoaXRlIHJlcHJlc2VudGF0aW9uIG9mIGhpcyBtYXN0ZXJwaWVjZSwgY2FuIHlvdSBoZWxwIFMuVy5FLlIuQy4gaWRlbnRpZnkgaW4gaG93IG1hbnkgbG9jYXRpb25zIGhpcyBwYWludGluZyBtaWdodCBiZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnNpc3RzIG9mIDQgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBoPHN1Yj5wPFwvc3ViPiB3PHN1Yj5wPFwvc3ViPiBoPHN1Yj5tPFwvc3ViPiB3PHN1Yj5tPFwvc3ViPiwgdGhlIGhlaWdodCBhbmQgd2lkdGggb2YgdGhlIHBhaW50aW5nIGhlIG5lZWRzIHRvIGZpbmQsIGFuZCB0aGUgaGVpZ2h0IGFuZCB3aWR0aCBvZiBoaXMgbWFzdGVycGllY2UsIHJlc3BlY3RpdmVseS4gVGhlIG5leHQgaDxzdWI+cDxcL3N1Yj4gbGluZXMgaGF2ZSB3PHN1Yj5wPFwvc3ViPiBsb3dlci1jYXNlIGNoYXJhY3RlcnMgcmVwcmVzZW50aW5nIGhpcyBwYWludGluZy4gQWZ0ZXIgdGhhdCwgdGhlIG5leHQgaDxzdWI+bTxcL3N1Yj4gbGluZXMgaGF2ZSB3PHN1Yj5tPFwvc3ViPiBsb3dlci1jYXNlIGNoYXJhY3RlcnMgcmVwcmVzZW50aW5nIGhpcyBtYXN0ZXJwaWVjZS4gRWFjaCBjaGFyYWN0ZXIgd2lsbCBiZSBlaXRoZXIgJmxzcXVvO3gmcnNxdW87IG9yICZsc3F1bztvJnJzcXVvOy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIGxvY2F0aW9ucyB3aGVyZSBoaXMgcGFpbnRpbmcgbWlnaHQgYmUuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBwYWludGluZyBjb3VsZCBiZSBpbiBmb3VyIGxvY2F0aW9ucyBhcyBzaG93biBpbiB0aGUgZm9sbG93aW5nIHBpY3R1cmUuIFR3byBvZiB0aGUgbG9jYXRpb25zIG92ZXJsYXAuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9wYWludGluZy5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjRweDsgd2lkdGg6MTIxcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cblx0PGxpPjEgJmxlOyBoPHN1Yj5wPFwvc3ViPiwgdzxzdWI+cDxcL3N1Yj4gJmxlOyAyIDAwMDxcL2xpPlxuXHQ8bGk+MSAmbGU7IGg8c3ViPm08XC9zdWI+LCB3PHN1Yj5tPFwvc3ViPiAmbGU7IDIgMDAwPFwvbGk+XG5cdDxsaT5oPHN1Yj5wPFwvc3ViPiAmbGU7IGg8c3ViPm08XC9zdWI+PFwvbGk+XG5cdDxsaT53PHN1Yj5wPFwvc3ViPiAmbGU7IHc8c3ViPm08XC9zdWI+PFwvbGk+XG48XC91bD5cbiJ9XQ==

출처

ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2014 J번

  • 문제의 오타를 찾은 사람: cokcjswo
  • 문제를 번역한 사람: kks227