시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 120 9 6 25.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+XHJcblx0PGxpPlx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWQ2MDRcdWM3YWMgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YzVkMCBcdWMzNjhcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwIFhcdWI5N2MgXHVjNzdkXHViMjk0XHViMmU0LiBcdWM3NzQgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YjljOFx1YjJlNCBcdWIyZTRcdWI5NzRcdWJhNzAsIFx1YzljMFx1YjJhNVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM3OTBcdWMyZTBcdWM1ZDBcdWFjOGMgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3N2RcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFhcdWJjODggOTBcdWIzYzQgXHVkNjhjXHVjODA0XHVjNzQ0IFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYzI5XHVkNWE1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzQgXHVjMmU0XHVkNWQ4XHVkMzEwXHVjNzU4IFx1YWNiZFx1YWNjNFx1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDRcdWIyZTRcdWJhNzQsIDE4MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWM3NDQgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWQ1NWMgXHVjZTc4IFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWIzNmJcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTc0IFx1YjE5M1x1YzU1OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWIzNmJcdWM3NzQgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0LCBcdWM5ODlcdWMyZGMgXHViMzZiXHVjNWQwIFx1YWM3OFx1YjgyNCBcdWM4ZmRcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVhYzAwIFx1YzhmZFx1YjI5NFx1YjM3MCBcdWJhODcgXHVjZDA4XHVhYzAwIFx1YWM3OFx1YjlhY1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgTSwgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiwgTSAmbGU7IDUwLCAxICZsZTsgSyAmbGU7IDUpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMzZiXHVjNzc0IFx1YzEyNFx1Y2U1OFx1YjQxYyBcdWFjZjNcdWM3NTggXHVkNTg5IFhcdWM2NDAgXHVjNWY0IFlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIwOThcdWJhMzhcdWM5YzAgXHVjOTA0XHVjNzQwIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjMTI0XHViYTg1XHVjNzc0XHViYTcwLCAxXHViYzg4IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YmQ4MFx1ZDEzMCBLXHViYzg4XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggWGkgWWlcdWM2NDAgXHViYzE0XHViNzdjXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWQ1YTUgQ2lcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoQ2kgPSBVKFx1YzcwNCksIFIoXHVjNjI0XHViOTc4XHVjYWJkKSwgRChcdWM1NDRcdWI3OTgpLCBMKFx1YzY3Y1x1Y2FiZCkpPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IE4gJnRpbWVzOyBNIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1ODlcdWI4MmNcdWM3NDQgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0IFx1YzZkMFx1YzE4Y1x1YjI5NCAwXHVhY2ZjIDlcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM3NzRcdWJhNzAsIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NCBpXHVjNTQ0ICh4LHkpXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYThcdWI0ZTAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVhYzAwIFx1YzhmZFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YjJlOFx1YzcwNDogXHVjZDA4KSBcdWI5Y2NcdWM1N2QsIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWJhYThcdWI0NTAgXHVjOGZkXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCwgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU2MjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCQUtURVJJSkUiLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgaXMgYm9yZWQgaW4gY2hlbWlzdHJ5IGNsYXNzIHlldCBhZ2Fpbi4gVGhpcyB0aW1lLCBoZSYjMzk7cyBwbGF5aW5nIHdpdGggaW50ZWxsaWdlbnQgYmFjdGVyaWEuIEhlIGhhcyBhcnJhbmdlZCBoaXMgSyBiYWN0ZXJpYSBvbiBhIHJlY3Rhbmd1bGFyIGJvYXJkIGRpdmlkZWQgaW4gTiByb3dzLCBsYWJlbGxlZCB3aXRoIG51bWJlcnMgZnJvbSAxIHRvIE4gc3RhcnRpbmcgZnJvbSB0aGUgdG9wLCBhbmQgTSBjb2x1bW5zLCBsYWJlbGxlZCB3aXRoIG51bWJlcnMgZnJvbSAxIHRvIE0gc3RhcnRpbmcgZnJvbSB0aGUgbGVmdC48XC9wPlxyXG5cclxuPHA+RWFjaCBiYWN0ZXJpdW0gYmVnaW5zIGl0cyBhZHZlbnR1cmUgaW4gYSBjZXJ0YWluIGNlbGwsIGZhY2luZyBvbmUgb2YgdGhlIGZvdXIgbmVpZ2hib3VyaW5nIGNlbGxzLCBhbmQgY2FycmllcyBvdXQgdGhlIGZvbGxvd2luZyBhY3Rpb25zIGV2ZXJ5IHNlY29uZDo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5SZWFkcyB0aGUgbnVtYmVyIFggZGVkaWNhdGVkIHRvIHRoYXQgYmFjdGVyaXVtIGluIHRoZSBjdXJyZW50IGNlbGwuPFwvbGk+XHJcblx0PGxpPlR1cm5zIDkwIGRlZ3JlZXMgY2xvY2t3aXNlLCBYIHRpbWVzLjxcL2xpPlxyXG5cdDxsaT5JZiBpdCBpcyBmYWNpbmcgYSBjZWxsIG91dHNpZGUgdGhlIGJvYXJkLCBpdCB0dXJucyAxODAgZGVncmVlcy48XC9saT5cclxuXHQ8bGk+RmluYWxseSwgaXQgbW92ZXMgdG8gdGhlIGNlbGwgdGhhdCBpdCBpcyBmYWNpbmcuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+THVrYSBoYXMgcGxhY2VkIGEgdHJhcCBpbiBvbmUgY2VsbC4gVGhlIHRyYXAgd2lsbCBhY3RpdmF0ZSBhbmQga2lsbCB0aGUgYmFjdGVyaWEgYXMgc29vbiBhcyB0aGV5IGFsbCBzdGVwIG9uIHRoYXQgY2VsbCBpbiB0aGUgc2FtZSBzZWNvbmQuPFwvcD5cclxuXHJcbjxwPlNpbmNlIEx1a2Egb25seSBoYXMgdHdvIGhvdXJzIG9mIGNoZW1pc3RyeSBjbGFzcyB0b2RheSwgaGVscCBoaW0gZGV0ZXJtaW5lIGhvdyBsb25nIHRoZSBnYW1lIHdpbGwgbGFzdCwgaW4gc2Vjb25kcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VycyBOICgzICZsZTsgTiAmbGU7IDUwKSwgTSAoMyAmbGU7IE0gJmxlOyA1MCksIGFuZCBLICgxICZsZTsgSyAmbGU7IDUpLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXJzIFggYW5kIFksIHRoZSByb3cgYW5kIGNvbHVtbiB3aGVyZSBMdWthIGhhcyBwbGFjZWQgdGhlIHRyYXAuPFwvcD5cclxuXHJcbjxwPlRoZSByZW1haW5kZXIgb2YgdGhlIGlucHV0IGNvbnNpc3RzIG9mIGJhY3RlcmlhIGRlc2NyaXB0aW9ucywgZm9yIGVhY2ggYmFjdGVyaXVtIGkgZnJvbSAxIHRvIEs6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dHdvIHBvc2l0aXZlIGludGVnZXJzIFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiAmbmRhc2g7IHRoZSByb3cgYW5kIGNvbHVtbiBvZiB0aGUgc3RhcnRpbmcgY2VsbCBvZiBiYWN0ZXJpdW0gaSwgYW5kIHRoZSBjaGFyYWN0ZXIgQzxzdWI+aTxcL3N1Yj4gcmVwcmVzZW50aW5nIHRoZSBzdGFydGluZyBkaXJlY3Rpb24gdGhhdCB0aGUgYmFjdGVyaXVtIGlzIGZhY2luZyAoVSAmbmRhc2g7IHVwLCBSICZuZGFzaDsgcmlnaHQsIEQgJm5kYXNoOyBkb3duLCBMICZuZGFzaDsgbGVmdCkuPFwvbGk+XHJcblx0PGxpPiZuYnNwO04gYnkgTSBtYXRyaXggb2YgZGlnaXRzIGJldHdlZW4gMCBhbmQgOSwgaW5jbHVzaXZlOyB0aGUgZGlnaXQgaW4gcm93IHggYW5kIGNvbHVtbiB5IHJlcHJlc2VudHMgdGhlIG51bWJlciBpbiBjZWxsICh4LCB5KSBkZWRpY2F0ZWQgdG8gYmFjdGVyaXVtIGkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSB0b3RhbCBkdXJhdGlvbiBvZiBMdWthJiMzOTtzIGdhbWUsIGluIHNlY29uZHMuIElmIHRoZSBnYW1lIHdpbGwgbmV2ZXIgZW5kLCBvdXRwdXQgLTEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d