시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB39741582118538.512%

문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

예제 입력 1

3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE0NDY2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDYiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzE4Y1x1YWMwMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHVhYzA0IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWFkZjhcdWIwZTUgXHVhZTM4XHVjNzc0IFx1YjljZVx1YzU0NFx1YzExY1x1Yzc3NFx1YjJlNC4gXHVjODc0XHVjNzU4IFx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzQgXHViMTA4XHViYjM0IFx1YjljZVx1YzU0NFx1YzExYywgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YzljMCBcdWM1NGFcdWFjZTBcdWMxMWNcdWIyOTQgXHViY2M0XHViODVjIFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJkMCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzRcdWM3NTggXHViMThkXHVjN2E1XHVjNWQwIFx1YjMwMFx1YjMwMFx1YzgwMVx1Yzc3OCBcdWFjMWNcdWQzYjhcdWM3NzQgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNzkxXHVjNzQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYTlcdWNkMDhcdWM5YzBcdWFjMDAgTiZ0aW1lcztOICgyICZsZTsgTiAmbGU7IDEwMCkgXHVhY2E5XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJhYTlcdWNkMDhcdWM5YzAgXHVjMGFjXHVjNzc0XHViMjk0IFx1Yzc3Y1x1YmMxOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM3OTBcdWM3MjBcdWI4NmRcdWFjOGMgXHVhYzc0XHViMTA4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1YWRmOCBcdWM5MTEgXHVjNzdjXHViZDgwXHViMjk0IFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWM1N2MgXHVkNTVjXHViMmU0LiA8YSBocmVmPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMTQ0NjlcIj5cdWIxOGRcdWM3YTVcdWM3NTggXHViYzE0XHVhZTY1XHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc0MCBcdWM2YjhcdWQwYzBcdWI5YWM8XC9hPlx1YWMwMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHVjMThjXHVhYzAwIFx1YjE4ZFx1YzdhNSBcdWJjMTZcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1Yzc3Y1x1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPktcdWI5YzhcdWI5YWNcdWM3NTggKDEgJmxlOyBLICZsZTsgMTAwLEsgJmxlOyBOPHN1cD4yPFwvc3VwPikgXHVjMThjXHVhYzAwIFx1Yzg3NFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjMThjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWMxOGNcdWIyOTQgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViOWNjXHViMDk4XHVjOWMwIFx1YmFiYiBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2YwIFx1YzE4Y1x1YWMwMCBcdWJhODcgXHVjMzBkXHVjNzc4XHVjOWMwIFx1YzEzOFx1YzViNFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgTiwgSywgUlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBSXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWUzOFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUzOFx1Yzc0MCBcdWMwYzFcdWQ1NThcdWM4OGNcdWM2YjBcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWJhYTlcdWNkMDhcdWM5YzBcdWI5N2MgXHVjNzg3XHVhY2UwLCByJm5ic3A7YyZuYnNwO3ImcHJpbWU7IGMmcHJpbWU7XHVjNzU4IFx1ZDYxNVx1ZDBkYyAoXHVkNTg5LCBcdWM1ZjQsIFx1ZDU4OSwgXHVjNWY0KVx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMyMThcdWIyOTQgMSBcdWM3NzRcdWMwYzEgTiBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgS1x1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNzU4IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWMxOGNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YjljY1x1YjBhMCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YzE4Y1x1YWMwMCBcdWJhODcgXHVjMzBkXHVjNzc4XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNDQ2NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoeSBEaWQgdGhlIENvdyBDcm9zcyB0aGUgUm9hZCBJSUkgKFNpbHZlcikiLCJkZXNjcmlwdGlvbiI6IjxwPldoeSBkaWQgdGhlIGNvdyBjcm9zcyB0aGUgcm9hZD8gV2VsbCwgb25lIHJlYXNvbiBpcyB0aGF0IEZhcm1lciBKb2huJiMzOTtzIGZhcm0gc2ltcGx5IGhhcyBhIGxvdCBvZiByb2FkcywgbWFraW5nIGl0IGltcG9zc2libGUgZm9yIGhpcyBjb3dzIHRvIHRyYXZlbCBhcm91bmQgd2l0aG91dCBjcm9zc2luZyBtYW55IG9mIHRoZW0uPFwvcD5cclxuXHJcbjxwPkZKJiMzOTtzIGZhcm0gaXMgYXJyYW5nZWQgYXMgYW4mbmJzcDtOJnRpbWVzO04gc3F1YXJlIGdyaWQgb2YgZmllbGRzICgyICZsZTsgTiAmbGU7IDEwMCksIENlcnRhaW4gcGFpcnMgb2YgYWRqYWNlbnQgZmllbGRzIChlLmcuLCBub3J0aC1zb3V0aCBvciBlYXN0LXdlc3QpIGFyZSBzZXBhcmF0ZWQgYnkgcm9hZHMsIGFuZCBhIHRhbGwgZmVuY2UgcnVucyBhcm91bmQgdGhlIGV4dGVybmFsIHBlcmltZXRlciBvZiB0aGUgZW50aXJlIGdyaWQsIHByZXZlbnRpbmcgY293cyBmcm9tIGxlYXZpbmcgdGhlIGZhcm0uIENvd3MgY2FuIG1vdmUgZnJlZWx5IGZyb20gYW55IGZpZWxkIHRvIGFueSBvdGhlciBhZGphY2VudCBmaWVsZCAobm9ydGgsIGVhc3QsIHNvdXRoLCBvciB3ZXN0KSwgYWx0aG91Z2ggdGhleSBwcmVmZXIgbm90IHRvIGNyb3NzIHJvYWRzIHVubGVzcyBhYnNvbHV0ZWx5IG5lY2Vzc2FyeS48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlJm5ic3A7SyZuYnNwO2Nvd3MgKDEgJmxlOyBLICZsZTsgMTAwLEsgJmxlOyBOPHN1cD4yPFwvc3VwPikgb24gRkomIzM5O3MgZmFybSwgZWFjaCBsb2NhdGVkIGluIGEgZGlmZmVyZW50IGZpZWxkLiBBIHBhaXIgb2YgY293cyBpcyBzYWlkIHRvIGJlICZxdW90O2Rpc3RhbnQmcXVvdDsgaWYsIGluIG9yZGVyIGZvciBvbmUgY293IHRvIHZpc2l0IHRoZSBvdGhlciwgaXQgaXMgbmVjZXNzYXJ5IHRvIGNyb3NzIGF0IGxlYXN0IG9uZSByb2FkLiBQbGVhc2UgaGVscCBGSiBjb3VudCB0aGUgbnVtYmVyIG9mIGRpc3RhbnQgcGFpcnMgb2YgY293cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zJm5ic3A7TiwmbmJzcDtLLCBhbmQmbmJzcDtSLiBUaGUgbmV4dCZuYnNwO1ImbmJzcDtsaW5lcyBkZXNjcmliZSZuYnNwO1ImbmJzcDtyb2FkcyB0aGF0IGV4aXN0IGJldHdlZW4gcGFpcnMgb2YgYWRqYWNlbnQgZmllbGRzLiBFYWNoIGxpbmUgaXMgb2YgdGhlIGZvcm0gciZuYnNwO2MmbmJzcDtyJnByaW1lOyBjJnByaW1lOyAoaW50ZWdlcnMgaW4gdGhlIHJhbmdlJm5ic3A7MSZoZWxsaXA7TiksIGluZGljYXRpbmcgYSByb2FkIGJldHdlZW4gdGhlIGZpZWxkIGluIChyb3cmbmJzcDtyLCBjb2x1bW4mbmJzcDtjKSBhbmQgdGhlIGFkamFjZW50IGZpZWxkIGluIChyb3cmbmJzcDtyJnByaW1lOywgY29sdW1uJm5ic3A7YyZwcmltZTspLiBUaGUgZmluYWwmbmJzcDtLJm5ic3A7bGluZXMgaW5kaWNhdGUgdGhlIGxvY2F0aW9ucyBvZiB0aGUmbmJzcDtLJm5ic3A7Y293cywgZWFjaCBzcGVjaWZpZWQgaW4gdGVybXMgb2YgYSByb3cgYW5kIGNvbHVtbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIGNvd3MgdGhhdCBhcmUgZGlzdGFudC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Silver 3번

  • 문제를 번역한 사람: jh05013