시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 238 66 35 31.532%

문제

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

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

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

입력

첫 번째 줄에 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+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWIzNTggXHVjNWI0XHViMjkwXHViMGEwLCBcdWM3YWNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNjA4XHVjMGMxXHVjZTU4IFx1YmFiYlx1ZDU1YyBcdWM4MDRcdWQ2NTRcdWI5N2MmbmJzcDtcdWJjMWJcdWFjZTAgXHViOWQwXHVjNTU4XHViMmU0LiZuYnNwO1x1YzgwNFx1ZDY1NFx1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NDAmbmJzcDtcdWM1NDRcdWM5YzEgXHVkMzE0XHViOWFjXHVjOWMwIFx1YzU0YVx1YzU1OFx1YjM1OCBcdWFkZjhcdWI5YmMgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMwYWNcdWFjYTBcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjN2FjXHVkNjAxXHVjNzc0XHViMjk0IFx1ZDA3MCBcdWFkZjhcdWI5YmNcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YjM3MCBcdWM1YjRcdWI1YTQgXHVhZGY4XHViOWJjXHViNGU0XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU4OFx1YjI5NFx1YzljMCBcdWFlMzBcdWI4NWRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWU0Y1x1YmEzOVx1YzVjOFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1Yzc5MFx1YWUzMCBcdWFjNzhcdWM3OTFcdWM3NTggXHVjNWI0XHViMjkwIFx1YWNmM1x1YzVkMCBcdWFkZjggXHVhZGY4XHViOWJjXHVjNzc0IFx1YzBhY1x1YzZhOVx1YjQxOFx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyZuYnNwO1x1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDc1MVx1YmMzMVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MWMgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWRmOFx1YWM3OCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHViOWNjXHViNGUwIFx1YWM3OFx1Yzc5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCZuYnNwO1x1YzdhY1x1ZDYwMVx1Yzc3NFx1YWMwMCBcdWFkZjhcdWI5YmNcdWM3NDQgXHVjYzNlXHViMjk0IFx1YWM4M1x1Yzc0NCZuYnNwO1x1YjNjNFx1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0XHVhYzAwPyZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgNFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggaDxzdWI+cDxcL3N1Yj4mbmJzcDt3PHN1Yj5wPFwvc3ViPiZuYnNwO2g8c3ViPm08XC9zdWI+Jm5ic3A7dzxzdWI+bTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDEgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YWRmOFx1YjliY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWM2NDAgXHViMTA4XHViZTQ0LCBcdWFjNzhcdWM3OTFcdWM3NTggXHViMTkyXHVjNzc0XHVjNjQwIFx1YjEwOFx1YmU0NFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzExYyBoPHN1Yj5wPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFkZjhcdWI5YmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBoPHN1Yj5tPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWM3OFx1Yzc5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjliY1x1Yzc0MCAmIzM5O3gmIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTtvJiMzOTtcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YWRmOFx1YjliY1x1Yzc1OCBcdWIxMDhcdWJlNDRcdWM2NDAgXHViMTkyXHVjNzc0XHViMjk0IDEgXHVjNzc0XHVjMGMxIDIwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwLCBcdWFjNzhcdWM3OTFcdWM3NTggXHViMTEzXHVjNzc0XHVjNjQwIFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWFjMDFcdWFjMDEgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YWRmOFx1YjliY1x1Yzc1OCBcdWIxMDhcdWJlNDRcdWM2NDAgXHViMTkyXHVjNzc0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGFjXHVjNmE5XHVkNTVjIFx1YWRmOFx1YjliY1x1Yzc3NCBcdWFjNzhcdWM3OTFcdWM1ZDBcdWMxMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvcGFpbnRpbmcucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI0cHg7IHdpZHRoOjEyMXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDUzOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBCaWcgUGFpbnRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPlNhbXVlbCBXLiBFLiBSLiBDcmFmdCBpcyBhbiBhcnRpc3Qgd2l0aCBhIGdyb3dpbmcgcmVwdXRhdGlvbi4gVW5mb3J0dW5hdGVseSwgdGhlIHBhaW50aW5ncyBoZSBzZWxscyBkbyBub3QgcHJvdmlkZSBoaW0gZW5vdWdoIG1vbmV5IGZvciBoaXMgZGFpbHkgZXhwZW5zZXMgcGx1cyB0aGUgbmV3IHN1cHBsaWVzIGhlIG5lZWRzLiBIZSBoYWQgYSBicmlsbGlhbnQgaWRlYSB5ZXN0ZXJkYXkgd2hlbiBoZSByYW4gb3V0IG9mIGJsYW5rIGNhbnZhczogJnF1b3Q7V2h5IGRvbiZyc3F1bzt0IEkgY3JlYXRlIGEgZ2lnYW50aWMgbmV3IHBhaW50aW5nLCBtYWRlIG9mIGFsbCB0aGUgdW5zZWxsYWJsZSBwYWludGluZ3MgSSBoYXZlLCBzdGl0Y2hlZCB0b2dldGhlcj8mcXVvdDsuIEFmdGVyIGEgZnVsbCBkYXkgb2Ygd29yaywgaGlzIG1hc3RlcnBpZWNlIHdhcyBjb21wbGV0ZS48XC9wPlxyXG5cclxuPHA+VGhhdCZyc3F1bztzIHdoZW4gaGUgcmVjZWl2ZWQgYW4gdW5leHBlY3RlZCBwaG9uZSBjYWxsOiBhIGNsaWVudCBzYXcgYSBwaG90b2dyYXBoIG9mIG9uZSBvZiBoaXMgcGFpbnRpbmdzIGFuZCBpcyB3aWxsaW5nIHRvIGJ1eSBpdCBub3chIEhlIGhhZCBmb3Jnb3R0ZW4gdG8gdGVsbCB0aGUgYXJ0IGdhbGxlcnkgdG8gcmVtb3ZlIGhpcyBvbGQgd29ya3MgZnJvbSB0aGUgY2F0YWxvZyEgSGUgd291bGQgdXN1YWxseSB3ZWxjb21lIGEgY2FsbCBsaWtlIHRoaXMsIGJ1dCBob3cgaXMgaGUgZ29pbmcgdG8gZmluZCBoaXMgb2xkIHdvcmsgaW4gdGhlIGh1Z2UgZmlndXJlIGluIGZyb250IG9mIGhpbT88XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBibGFjay1hbmQtd2hpdGUgcmVwcmVzZW50YXRpb24gb2YgaGlzIG9yaWdpbmFsIHBhaW50aW5nIGFuZCBhIGJsYWNrLWFuZC13aGl0ZSByZXByZXNlbnRhdGlvbiBvZiBoaXMgbWFzdGVycGllY2UsIGNhbiB5b3UgaGVscCBTLlcuRS5SLkMuIGlkZW50aWZ5IGluIGhvdyBtYW55IGxvY2F0aW9ucyBoaXMgcGFpbnRpbmcgbWlnaHQgYmU/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb25zaXN0cyBvZiA0IHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogaDxzdWI+cDxcL3N1Yj4gdzxzdWI+cDxcL3N1Yj4gaDxzdWI+bTxcL3N1Yj4gdzxzdWI+bTxcL3N1Yj4sIHRoZSBoZWlnaHQgYW5kIHdpZHRoIG9mIHRoZSBwYWludGluZyBoZSBuZWVkcyB0byBmaW5kLCBhbmQgdGhlIGhlaWdodCBhbmQgd2lkdGggb2YgaGlzIG1hc3RlcnBpZWNlLCByZXNwZWN0aXZlbHkuIFRoZSBuZXh0IGg8c3ViPnA8XC9zdWI+IGxpbmVzIGhhdmUgdzxzdWI+cDxcL3N1Yj4gbG93ZXItY2FzZSBjaGFyYWN0ZXJzIHJlcHJlc2VudGluZyBoaXMgcGFpbnRpbmcuIEFmdGVyIHRoYXQsIHRoZSBuZXh0IGg8c3ViPm08XC9zdWI+IGxpbmVzIGhhdmUgdzxzdWI+bTxcL3N1Yj4gbG93ZXItY2FzZSBjaGFyYWN0ZXJzIHJlcHJlc2VudGluZyBoaXMgbWFzdGVycGllY2UuIEVhY2ggY2hhcmFjdGVyIHdpbGwgYmUgZWl0aGVyICZsc3F1bzt4JnJzcXVvOyBvciAmbHNxdW87byZyc3F1bzsuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IGg8c3ViPnA8XC9zdWI+LCB3PHN1Yj5wPFwvc3ViPiAmbGU7IDIgMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBoPHN1Yj5tPFwvc3ViPiwgdzxzdWI+bTxcL3N1Yj4gJmxlOyAyIDAwMDxcL2xpPlxyXG5cdDxsaT5oPHN1Yj5wPFwvc3ViPiAmbGU7IGg8c3ViPm08XC9zdWI+PFwvbGk+XHJcblx0PGxpPnc8c3ViPnA8XC9zdWI+ICZsZTsgdzxzdWI+bTxcL3N1Yj48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgcG9zc2libGUgbG9jYXRpb25zIHdoZXJlIGhpcyBwYWludGluZyBtaWdodCBiZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIHBhaW50aW5nIGNvdWxkIGJlIGluIGZvdXIgbG9jYXRpb25zIGFzIHNob3duIGluIHRoZSBmb2xsb3dpbmcgcGljdHVyZS4gVHdvIG9mIHRoZSBsb2NhdGlvbnMgb3ZlcmxhcC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3BhaW50aW5nLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyNHB4OyB3aWR0aDoxMjFweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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