시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 121 10 7 28.000%

문제

지금은 화학 시간이다. 이번 시간에는 지능이 있는 박테리아를 연구하는 실험을 하고 있다. 상근이는 지루한 실험 대신 독특한 자신만의 실험을 하기로 했다.

먼저, 실험판을 N행 M열로 나눈다. 제일 윗 행은 1번, 마지막 행은 N번이고, 가장 왼쪽 열은 1번, 오른쪽은 M번 행이다. 그 다음 박테리아를 K마리 준비한다.

각 박테리아는 상근이가 지정한 칸에서 모험을 시작하게 되며, 위, 아래, 오른쪽 왼쪽 중 한 방향을 바라보고 있다. 각 박테리아는 일초동안 아래와 같은 일을 수행한다.

  1. 박테리아가 현재 있는 칸에 쓰여 있는 숫자 X를 읽는다. 이 숫자는 박테리아마다 다르며, 지능이 있는 박테리아이기 때문에 자신에게 해당하는 숫자를 읽을 수 있다.
  2. 시계방향으로 X번 90도 회전을 한다.
  3. 만약 바라보고 있는 방향에 있는 칸이 실험판의 경계를 넘어간다면, 180도 회전을 한다.
  4. 바라보고 있는 칸으로 한 칸 움직인다.

상근이는 한 칸에 덫을 설치해 놓았다. 모든 박테리아가 덫이 있는 칸으로 동시에 이동하면, 즉시 덫에 걸려 죽게 된다.

모든 박테리아가 죽는데 몇 초가 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 주어진다. (3 ≤ N, M ≤ 50, 1 ≤ K ≤ 5)

다음 줄에는 덫이 설치된 곳의 행 X와 열 Y가 주어진다.

나머지 줄은 박테리아에 대한 설명이며, 1번 박테리아부터 K번까지 순서대로 주어진다.

첫 줄에는 박테리아의 시작 위치 Xi Yi와 바라보고 있는 방향 Ci가 주어진다. (Ci = U(위), R(오른쪽), D(아래), L(왼쪽))

그 다음 줄에는 N × M 크기의 행렬이 주어진다. 행렬을 구성하는 원소는 0과 9를 포함하는 사이의 숫자이며, 박테리아 i아 (x,y)를 방문했을 때 해당하는 X이다.

출력

첫째 줄에 모든 박테리아가 죽는데 걸리는 시간을 출력한다. (단위: 초) 만약, 박테리아가 모두 죽지 않는다면, -1을 출력한다.

예제 입력 1

3 4 2
2 2
3 4 R
2327
6009
2112
3 2 R
1310
2101
1301

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjU2MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzljMFx1YWUwOFx1Yzc0MCBcdWQ2NTRcdWQ1NTkgXHVjMmRjXHVhYzA0XHVjNzc0XHViMmU0LiBcdWM3NzRcdWJjODggXHVjMmRjXHVhYzA0XHVjNWQwXHViMjk0IFx1YzljMFx1YjJhNVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHViOTdjIFx1YzVmMFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzljMFx1YjhlOFx1ZDU1YyBcdWMyZTRcdWQ1ZDggXHViMzAwXHVjMmUwIFx1YjNjNVx1ZDJiOVx1ZDU1YyBcdWM3OTBcdWMyZTBcdWI5Y2NcdWM3NTggXHVjMmU0XHVkNWQ4XHVjNzQ0IFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCwgXHVjMmU0XHVkNWQ4XHVkMzEwXHVjNzQ0IE5cdWQ1ODkgTVx1YzVmNFx1Yjg1YyBcdWIwOThcdWIyMDhcdWIyZTQuIFx1YzgxY1x1Yzc3YyBcdWM3MTcgXHVkNTg5XHVjNzQwIDFcdWJjODgsIFx1YjljOFx1YzljMFx1YjljOSBcdWQ1ODlcdWM3NDAgTlx1YmM4OFx1Yzc3NFx1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM1ZjRcdWM3NDAgMVx1YmM4OCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQwIE1cdWJjODggXHVkNTg5XHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yjk3YyBLXHViOWM4XHViOWFjIFx1YzkwMFx1YmU0NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOWMwXHVjODE1XHVkNTVjIFx1Y2U3OFx1YzVkMFx1YzExYyBcdWJhYThcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3MCwgXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM2N2NcdWNhYmQgXHVjOTExIFx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHViNzdjXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YjI5NCBcdWM3N2NcdWNkMDhcdWIzZDlcdWM1NDggXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM3N2NcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWQ2MDRcdWM3YWMgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MCBYXHViOTdjIFx1Yzc3ZFx1YjI5NFx1YjJlNC4gXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWI5YzhcdWIyZTQgXHViMmU0XHViOTc0XHViYTcwLCBcdWM5YzBcdWIyYTVcdWM3NzQgXHVjNzg4XHViMjk0IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzkwXHVjMmUwXHVjNWQwXHVhYzhjIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzdkXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBYXHViYzg4IDkwXHViM2M0IFx1ZDY4Y1x1YzgwNFx1Yzc0NCBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCBcdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmMyOVx1ZDVhNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzc0IFx1YzJlNFx1ZDVkOFx1ZDMxMFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWI5N2MgXHViMTE4XHVjNWI0XHVhYzA0XHViMmU0XHViYTc0LCAxODBcdWIzYzQgXHVkNjhjXHVjODA0XHVjNzQ0IFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYzE0XHViNzdjXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2U3OCBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHViMzZiXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU3NCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWFjMDAgXHViMzZiXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3M2NcdWI4NWMgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3NCwgXHVjOTg5XHVjMmRjIFx1YjM2Ylx1YzVkMCBcdWFjNzhcdWI4MjQgXHVjOGZkXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWM4ZmRcdWIyOTRcdWIzNzAgXHViYTg3IFx1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YWNcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4sIE0sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4sIE0gJmxlOyA1MCwgMSAmbGU7IEsgJmxlOyA1KTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjM2Ylx1Yzc3NCBcdWMxMjRcdWNlNThcdWI0MWMgXHVhY2YzXHVjNzU4IFx1ZDU4OSBYXHVjNjQwIFx1YzVmNCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMDk4XHViYTM4XHVjOWMwIFx1YzkwNFx1Yzc0MCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzEyNFx1YmE4NVx1Yzc3NFx1YmE3MCwgMVx1YmM4OCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWJkODBcdWQxMzAgS1x1YmM4OFx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IFhpIFlpXHVjNjQwIFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYzI5XHVkNWE1IENpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKENpID0gVShcdWM3MDQpLCBSKFx1YzYyNFx1Yjk3OFx1Y2FiZCksIEQoXHVjNTQ0XHViNzk4KSwgTChcdWM2N2NcdWNhYmQpKTxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBOICZ0aW1lczsgTSBcdWQwNmNcdWFlMzBcdWM3NTggXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTg5XHViODJjXHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWM2ZDBcdWMxOGNcdWIyOTQgMFx1YWNmYyA5XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjMjJiXHVjNzkwXHVjNzc0XHViYTcwLCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDQgaVx1YzU0NCAoeCx5KVx1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1ODhcdWM3NDQgXHViNTRjIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBYXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWM4ZmRcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWIyZThcdWM3MDQ6IFx1Y2QwOCkgXHViOWNjXHVjNTdkLCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWFjMDAgXHViYWE4XHViNDUwIFx1YzhmZFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQsIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjI3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQkFLVEVSSUpFIiwiZGVzY3JpcHRpb24iOiI8cD5MdWthIGlzIGJvcmVkIGluIGNoZW1pc3RyeSBjbGFzcyB5ZXQgYWdhaW4uIFRoaXMgdGltZSwgaGUmIzM5O3MgcGxheWluZyB3aXRoIGludGVsbGlnZW50IGJhY3RlcmlhLiBIZSBoYXMgYXJyYW5nZWQgaGlzIEsgYmFjdGVyaWEgb24gYSByZWN0YW5ndWxhciBib2FyZCBkaXZpZGVkIGluIE4gcm93cywgbGFiZWxsZWQgd2l0aCBudW1iZXJzIGZyb20gMSB0byBOIHN0YXJ0aW5nIGZyb20gdGhlIHRvcCwgYW5kIE0gY29sdW1ucywgbGFiZWxsZWQgd2l0aCBudW1iZXJzIGZyb20gMSB0byBNIHN0YXJ0aW5nIGZyb20gdGhlIGxlZnQuPFwvcD5cclxuXHJcbjxwPkVhY2ggYmFjdGVyaXVtIGJlZ2lucyBpdHMgYWR2ZW50dXJlIGluIGEgY2VydGFpbiBjZWxsLCBmYWNpbmcgb25lIG9mIHRoZSBmb3VyIG5laWdoYm91cmluZyBjZWxscywgYW5kIGNhcnJpZXMgb3V0IHRoZSBmb2xsb3dpbmcgYWN0aW9ucyBldmVyeSBzZWNvbmQ6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+UmVhZHMgdGhlIG51bWJlciBYIGRlZGljYXRlZCB0byB0aGF0IGJhY3Rlcml1bSBpbiB0aGUgY3VycmVudCBjZWxsLjxcL2xpPlxyXG5cdDxsaT5UdXJucyA5MCBkZWdyZWVzIGNsb2Nrd2lzZSwgWCB0aW1lcy48XC9saT5cclxuXHQ8bGk+SWYgaXQgaXMgZmFjaW5nIGEgY2VsbCBvdXRzaWRlIHRoZSBib2FyZCwgaXQgdHVybnMgMTgwIGRlZ3JlZXMuPFwvbGk+XHJcblx0PGxpPkZpbmFsbHksIGl0IG1vdmVzIHRvIHRoZSBjZWxsIHRoYXQgaXQgaXMgZmFjaW5nLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkx1a2EgaGFzIHBsYWNlZCBhIHRyYXAgaW4gb25lIGNlbGwuIFRoZSB0cmFwIHdpbGwgYWN0aXZhdGUgYW5kIGtpbGwgdGhlIGJhY3RlcmlhIGFzIHNvb24gYXMgdGhleSBhbGwgc3RlcCBvbiB0aGF0IGNlbGwgaW4gdGhlIHNhbWUgc2Vjb25kLjxcL3A+XHJcblxyXG48cD5TaW5jZSBMdWthIG9ubHkgaGFzIHR3byBob3VycyBvZiBjaGVtaXN0cnkgY2xhc3MgdG9kYXksIGhlbHAgaGltIGRldGVybWluZSBob3cgbG9uZyB0aGUgZ2FtZSB3aWxsIGxhc3QsIGluIHNlY29uZHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlcnMgTiAoMyAmbGU7IE4gJmxlOyA1MCksIE0gKDMgJmxlOyBNICZsZTsgNTApLCBhbmQgSyAoMSAmbGU7IEsgJmxlOyA1KS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VycyBYIGFuZCBZLCB0aGUgcm93IGFuZCBjb2x1bW4gd2hlcmUgTHVrYSBoYXMgcGxhY2VkIHRoZSB0cmFwLjxcL3A+XHJcblxyXG48cD5UaGUgcmVtYWluZGVyIG9mIHRoZSBpbnB1dCBjb25zaXN0cyBvZiBiYWN0ZXJpYSBkZXNjcmlwdGlvbnMsIGZvciBlYWNoIGJhY3Rlcml1bSBpIGZyb20gMSB0byBLOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnR3byBwb3NpdGl2ZSBpbnRlZ2VycyBYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj4gJm5kYXNoOyB0aGUgcm93IGFuZCBjb2x1bW4gb2YgdGhlIHN0YXJ0aW5nIGNlbGwgb2YgYmFjdGVyaXVtIGksIGFuZCB0aGUgY2hhcmFjdGVyIEM8c3ViPmk8XC9zdWI+IHJlcHJlc2VudGluZyB0aGUgc3RhcnRpbmcgZGlyZWN0aW9uIHRoYXQgdGhlIGJhY3Rlcml1bSBpcyBmYWNpbmcgKFUgJm5kYXNoOyB1cCwgUiAmbmRhc2g7IHJpZ2h0LCBEICZuZGFzaDsgZG93biwgTCAmbmRhc2g7IGxlZnQpLjxcL2xpPlxyXG5cdDxsaT4mbmJzcDtOIGJ5IE0gbWF0cml4IG9mIGRpZ2l0cyBiZXR3ZWVuIDAgYW5kIDksIGluY2x1c2l2ZTsgdGhlIGRpZ2l0IGluIHJvdyB4IGFuZCBjb2x1bW4geSByZXByZXNlbnRzIHRoZSBudW1iZXIgaW4gY2VsbCAoeCwgeSkgZGVkaWNhdGVkIHRvIGJhY3Rlcml1bSBpLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgdG90YWwgZHVyYXRpb24gb2YgTHVrYSYjMzk7cyBnYW1lLCBpbiBzZWNvbmRzLiBJZiB0aGUgZ2FtZSB3aWxsIG5ldmVyIGVuZCwgb3V0cHV0IC0xLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==