시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 536 127 63 27.511%

문제

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

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

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

입력

첫 번째 줄에 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+XHJcbiIsImhpbnQiOiI8cD4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3BhaW50aW5nLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyNHB4OyB3aWR0aDoxMjFweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA1MzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgQmlnIFBhaW50aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5TYW11ZWwgVy4gRS4gUi4gQ3JhZnQgaXMgYW4gYXJ0aXN0IHdpdGggYSBncm93aW5nIHJlcHV0YXRpb24uIFVuZm9ydHVuYXRlbHksIHRoZSBwYWludGluZ3MgaGUgc2VsbHMgZG8gbm90IHByb3ZpZGUgaGltIGVub3VnaCBtb25leSBmb3IgaGlzIGRhaWx5IGV4cGVuc2VzIHBsdXMgdGhlIG5ldyBzdXBwbGllcyBoZSBuZWVkcy4gSGUgaGFkIGEgYnJpbGxpYW50IGlkZWEgeWVzdGVyZGF5IHdoZW4gaGUgcmFuIG91dCBvZiBibGFuayBjYW52YXM6ICZxdW90O1doeSBkb24mcnNxdW87dCBJIGNyZWF0ZSBhIGdpZ2FudGljIG5ldyBwYWludGluZywgbWFkZSBvZiBhbGwgdGhlIHVuc2VsbGFibGUgcGFpbnRpbmdzIEkgaGF2ZSwgc3RpdGNoZWQgdG9nZXRoZXI/JnF1b3Q7LiBBZnRlciBhIGZ1bGwgZGF5IG9mIHdvcmssIGhpcyBtYXN0ZXJwaWVjZSB3YXMgY29tcGxldGUuPFwvcD5cclxuXHJcbjxwPlRoYXQmcnNxdW87cyB3aGVuIGhlIHJlY2VpdmVkIGFuIHVuZXhwZWN0ZWQgcGhvbmUgY2FsbDogYSBjbGllbnQgc2F3IGEgcGhvdG9ncmFwaCBvZiBvbmUgb2YgaGlzIHBhaW50aW5ncyBhbmQgaXMgd2lsbGluZyB0byBidXkgaXQgbm93ISBIZSBoYWQgZm9yZ290dGVuIHRvIHRlbGwgdGhlIGFydCBnYWxsZXJ5IHRvIHJlbW92ZSBoaXMgb2xkIHdvcmtzIGZyb20gdGhlIGNhdGFsb2chIEhlIHdvdWxkIHVzdWFsbHkgd2VsY29tZSBhIGNhbGwgbGlrZSB0aGlzLCBidXQgaG93IGlzIGhlIGdvaW5nIHRvIGZpbmQgaGlzIG9sZCB3b3JrIGluIHRoZSBodWdlIGZpZ3VyZSBpbiBmcm9udCBvZiBoaW0/PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgYmxhY2stYW5kLXdoaXRlIHJlcHJlc2VudGF0aW9uIG9mIGhpcyBvcmlnaW5hbCBwYWludGluZyBhbmQgYSBibGFjay1hbmQtd2hpdGUgcmVwcmVzZW50YXRpb24gb2YgaGlzIG1hc3RlcnBpZWNlLCBjYW4geW91IGhlbHAgUy5XLkUuUi5DLiBpZGVudGlmeSBpbiBob3cgbWFueSBsb2NhdGlvbnMgaGlzIHBhaW50aW5nIG1pZ2h0IGJlPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29uc2lzdHMgb2YgNCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IGg8c3ViPnA8XC9zdWI+IHc8c3ViPnA8XC9zdWI+IGg8c3ViPm08XC9zdWI+IHc8c3ViPm08XC9zdWI+LCB0aGUgaGVpZ2h0IGFuZCB3aWR0aCBvZiB0aGUgcGFpbnRpbmcgaGUgbmVlZHMgdG8gZmluZCwgYW5kIHRoZSBoZWlnaHQgYW5kIHdpZHRoIG9mIGhpcyBtYXN0ZXJwaWVjZSwgcmVzcGVjdGl2ZWx5LiBUaGUgbmV4dCBoPHN1Yj5wPFwvc3ViPiBsaW5lcyBoYXZlIHc8c3ViPnA8XC9zdWI+IGxvd2VyLWNhc2UgY2hhcmFjdGVycyByZXByZXNlbnRpbmcgaGlzIHBhaW50aW5nLiBBZnRlciB0aGF0LCB0aGUgbmV4dCBoPHN1Yj5tPFwvc3ViPiBsaW5lcyBoYXZlIHc8c3ViPm08XC9zdWI+IGxvd2VyLWNhc2UgY2hhcmFjdGVycyByZXByZXNlbnRpbmcgaGlzIG1hc3RlcnBpZWNlLiBFYWNoIGNoYXJhY3RlciB3aWxsIGJlIGVpdGhlciAmbHNxdW87eCZyc3F1bzsgb3IgJmxzcXVvO28mcnNxdW87LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBoPHN1Yj5wPFwvc3ViPiwgdzxzdWI+cDxcL3N1Yj4gJmxlOyAyIDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgaDxzdWI+bTxcL3N1Yj4sIHc8c3ViPm08XC9zdWI+ICZsZTsgMiAwMDA8XC9saT5cclxuXHQ8bGk+aDxzdWI+cDxcL3N1Yj4gJmxlOyBoPHN1Yj5tPFwvc3ViPjxcL2xpPlxyXG5cdDxsaT53PHN1Yj5wPFwvc3ViPiAmbGU7IHc8c3ViPm08XC9zdWI+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIGxvY2F0aW9ucyB3aGVyZSBoaXMgcGFpbnRpbmcgbWlnaHQgYmUuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBwYWludGluZyBjb3VsZCBiZSBpbiBmb3VyIGxvY2F0aW9ucyBhcyBzaG93biBpbiB0aGUgZm9sbG93aW5nIHBpY3R1cmUuIFR3byBvZiB0aGUgbG9jYXRpb25zIG92ZXJsYXAuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9wYWludGluZy5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjRweDsgd2lkdGg6MTIxcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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