시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9847 2192 1501 21.669%

문제

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫번째 정수는 행, 두번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데,  정수 X와 문자 C로 이루어져 있으며. X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 방향을 변경 한다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

예제 입력 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 1

9

예제 입력 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2

21

예제 입력 3

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

예제 출력 3

13
W3sicHJvYmxlbV9pZCI6IjMxOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjNDAiLCJkZXNjcmlwdGlvbiI6IjxwPiZuYnNwOyYjMzk7RHVtbXkmIzM5OyBcdWI3N2NcdWIyOTQgXHViM2M0XHVjMmE0XHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YjI5NCBcdWJjNDBcdWM3NzQgXHViMDk4XHVjNjQwXHVjMTFjIFx1YWUzMFx1YzViNFx1YjJlNFx1YjJjOFx1YjI5NFx1YjM3MCwgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YmEzOVx1YzczY1x1YmE3NCBcdWJjNDAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YjI5OFx1YzViNFx1YjA5Y1x1YjJlNC4gXHViYzQwXHVjNzc0IFx1Yzc3NFx1YjlhY1x1YzgwMFx1YjlhYyBcdWFlMzBcdWM1YjRcdWIyZTRcdWIyYzhcdWIyZTRcdWFjMDAgXHViY2JkIFx1YjYxMFx1YjI5NCBcdWM3OTBcdWFlMzBcdWM3OTBcdWMyZTBcdWM3NTggXHViYWI4XHVhY2ZjIFx1YmQ4MFx1YjUyYVx1ZDc4OFx1YmE3NCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgTnhOIFx1YzgxNVx1YzBhY1x1YWMwMSZuYnNwO1x1YmNmNFx1YjRkY1x1YzcwNFx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWI0MThcdWFjZTAsIFx1YmE4N1x1YmE4NyBcdWNlNzhcdWM1ZDBcdWIyOTQmbmJzcDtcdWMwYWNcdWFjZmNcdWFjMDAgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViY2Y0XHViNGRjXHVjNzU4IFx1YzBjMVx1ZDU1OFx1Yzg4Y1x1YzZiMCBcdWIwNWRcdWM1ZDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzJkY1x1Yzc5MVx1ZDU2MFx1YjU0YyBcdWJjNDBcdWM3NDAgXHViOWU4XHVjNzA0IFx1YjllOFx1Yzg4Y1x1Y2UyMVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjZTAgXHViYzQwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YjJlNC4gXHViYzQwXHVjNzQwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHVkNWE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjNDBcdWM3NDAgXHViOWU0IFx1Y2QwOFx1YjljOFx1YjJlNCBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAgXHViYzQwXHVjNzQwIFx1YmFiOFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIyOThcdWI4MjQmbmJzcDtcdWJhMzhcdWI5YWNcdWI5N2MmbmJzcDtcdWIyZTRcdWM3NGNcdWNlNzhcdWM1ZDAgXHVjNzA0XHVjZTU4XHVjMmRjXHVkMGE4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5Y2NcdWM1N2QgXHVjNzc0XHViM2Q5XHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWFkZjggXHVjZTc4XHVjNWQwIFx1Yzc4OFx1YjM1OCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNWM2XHVjNWI0XHVjOWMwXHVhY2UwIFx1YWYyY1x1YjlhY1x1YjI5NCBcdWM2YzBcdWM5YzFcdWM3NzRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5Y2NcdWM1N2QgXHVjNzc0XHViM2Q5XHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0LCBcdWJhYjhcdWFlMzhcdWM3NzRcdWI5N2MgXHVjOTA0XHVjNWVjXHVjMTFjIFx1YWYyY1x1YjlhY1x1YWMwMCBcdWM3MDRcdWNlNThcdWQ1NWMgXHVjZTc4XHVjNzQ0IFx1YmU0NFx1YzZjY1x1YzkwMFx1YjJlNC4gXHVjOTg5LCBcdWJhYjhcdWFlMzhcdWM3NzRcdWIyOTQgXHViY2MwXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMwYWNcdWFjZmNcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YmM0MFx1Yzc1OCBcdWM3NzRcdWIzZDlcdWFjYmRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YmE4NyBcdWNkMDhcdWM1ZDAgXHViMDVkXHViMDk4XHViMjk0XHVjOWMwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOFx1YzkwNFx1YzVkMCBcdWJjZjRcdWI0ZGNcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVjMGFjXHVhY2ZjXHVjNzU4IFx1YWMxY1x1YzIxOCZuYnNwO0tcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IEsgJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjY2FiXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCZuYnNwO1x1ZDU4OSwgXHViNDUwXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCZuYnNwO1x1YzVmNCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiZuYnNwO1x1YzBhY1x1YWNmY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHViYWE4XHViNDUwIFx1YjJlNFx1Yjk3NFx1YmE3MCwgXHViOWU4IFx1YzcwNCBcdWI5ZTggXHVjODhjXHVjZTIxICgxXHVkNTg5IDFcdWM1ZjQpIFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmM0MFx1Yzc1OCBcdWJjMjlcdWQ1YTUgXHViY2MwXHVkNjU4IFx1ZDY5Zlx1YzIxOCBMIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTCAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIExcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmM0MFx1Yzc1OCBcdWJjMjlcdWQ1YTUgXHViY2MwXHVkNjU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsICZuYnNwO1x1YzgxNVx1YzIxOCBYXHVjNjQwIFx1YmIzOFx1Yzc5MCBDXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAuIFhcdWNkMDhcdWFjMDAgXHViMDVkXHViMDljIFx1YjRhNFx1YzVkMCBcdWM2N2NcdWNhYmQoQ1x1YWMwMCAmIzM5O0wmIzM5OykgXHViNjEwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZChDXHVhYzAwICYjMzk7RCYjMzk7KVx1Yjg1YyBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViY2MwXHVhY2JkJm5ic3A7XHVkNTVjXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gWFx1YjI5NCAxMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmMyOVx1ZDVhNSBcdWM4MDRcdWQ2NTggXHVjODE1XHViY2Y0XHViMjk0IFhcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViYTg3IFx1Y2QwOFx1YzVkMCBcdWIwNWRcdWIwOThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxOTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJ6bWlqYSIsImRlc2NyaXB0aW9uIjoiPHA+T25lIG9mIHRoZSBtb3N0IHBvcHVsYXIgRE9TIGdhbWVzIGlzICYjMzk7RHVtbXkmIzM5Oy4gVGhlIHNuYWtlIGlzIGNyYXdsaW5nIHRocm91Z2ggdGhlIGJvYXJkIGFuZCBlYXRpbmcgYXBwbGVzIHRoYXQgaW5jcmVhc2UgaXRzIGxlbmd0aC4gVGhlIGdhbWUgZW5kcyB3aGVuIHRoZSBzbmFrZSBidW1wcyBpbnRvIGl0c2VsZiBvciBpbnRvIHRoZSB3YWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HYW1lIGJvYXJkIGNvbnNpc3RzIG9mIE54TiBzcXVhcmVzIGFycmFuZ2VkIGluIE4gcm93cyBhbmQgTiBjb2x1bW5zLCBhbmQgc29tZSBzcXVhcmVzIGNvbnRhaW4gYXBwbGVzLiBBcm91bmQgdGhlIGJvYXJkIHRoZXJlIGlzIGEgd2FsbC4gQXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgZ2FtZSwgdGhlIHNuYWtlIGlzIGxvY2F0ZWQgaW4gdGhlIHRvcC1sZWZ0IGNvcm5lciwgaXRzIGxlbmd0aCBpcyBlcXVhbCB0byAxIGFuZCBpdHMgaGVhZCBpcyBkaXJlY3RlZCB0b3dhcmRzIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5TbmFrZSBpcyBjcmF3bGluZyBieSBjaGFuZ2luZyBpdHMgcG9zaXRpb24gZHVyaW5nIGVhY2ggc2Vjb25kIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmZpcnN0LCBzbmFrZSBleHRlbmRzIGl0cyBsZW5ndGggYnkgc3ByZWFkaW5nIHRvIHRoZSBuZXh0IHNxdWFyZSBpbiBmcm9udCBvZiB0aGUgaGVhZCAoaS5lLiBpbiB0aGUgZGlyZWN0aW9uIG9mIHRoZSBoZWFkKSw8XC9saT5cclxuXHQ8bGk+aWYgdGhlcmUgaXMgYW4gYXBwbGUgb24gdGhhdCBzcXVhcmUsIHRhaWwgb2YgdGhlIHNuYWtlIGRvZXMgbm90IG1vdmUgKGhlbmNlLCBpdHMgbGVuZ3RoIGlzIGluY3JlYXNlZCBieSAxIGluIHRoaXMgc3RlcCksPFwvbGk+XHJcblx0PGxpPmlmIHRoZXJlIGlzIG5vIGFwcGxlLCBsYXN0IHNxdWFyZSBvZiB0aGUgdGFpbCBpcyBlcmFzZWQgKGhlbmNlLCBpdHMgbGVuZ3RoIHN0YXlzIHVuY2hhbmdlZCkmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Qb3NpdGlvbnMgb2YgdGhlIGFwcGxlcyBhbmQgbW92ZW1lbnRzIG9mIHRoZSBzbmFrZSBhcmUgZ2l2ZW4uIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBudW1iZXIgb2Ygc2Vjb25kcyB1bnRpbCB0aGUgZ2FtZSBlbmRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDIgJmxlOyBOICZsZTsgMTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIEssIDAgJmxlOyBLICZsZTsgMTAwLCB0aGUgbnVtYmVyIG9mIGFwcGxlcyBvbiB0aGUgYm9hcmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyBLIGxpbmVzIGNvbnRhaW4gY29vcmRpbmF0ZXMgb2YgYXBwbGVzIG9uIHRoZSBib2FyZC4gRmlyc3QgbnVtYmVyIGRlbm90ZXMgdGhlIHJvdyBhbmQgc2Vjb25kIG51bWJlciBkZW5vdGVzIHRoZSBjb2x1bW4gb2YgdGhlIGJvYXJkIHdoZXJlIHRoZSBhcHBsZSBpcyBzaXR1YXRlZC4gVGhlcmUgd2lsbCBiZSBubyBhcHBsZSBhdCB0aGUgdG9wLWxlZnQgY29ybmVyIG9mIHRoZSBib2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBudW1iZXIgTCwgMSAmbGU7IEwgJmxlOyAxMDAsIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIHNuYWtlIG1ha2VzIGEgdHVybi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEwgbGluZXMgY29udGFpbnMgdGhlIGRlc2NyaXB0aW9uIG9mIG9uZSB0dXJuLiBBIHNpbmdsZSB0dXJuIGlzIGRlc2NyaWJlZCBieSBhIG51bWJlciBYIChwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxMCwwMDApIGFuZCBhIGNoYXJhY3RlciBDLiBUaGlzIG1lYW5zIHRoYXQgdGhlIHNuYWtlIHJvdGF0ZXMgaXRzIGhlYWQgOTAgZGVncmVlcyBsZWZ0IChpZiBDIGlzICYjMzk7TCYjMzk7KSBvciByaWdodCAoaWYgQyBpcyAmIzM5O0QmIzM5OykgYXQgdGhlIGVuZCBvZiB0aGUgWHRoIHNlY29uZCZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIG51bWJlciBvZiBzZWNvbmRzIGZyb20gdGhlIHByb2JsZW0gc3RhdGVtZW50LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #1 - Juniors 2번

  • 문제의 오타를 찾은 사람: dlwocks31
  • 빠진 조건을 찾은 사람: doju joonas
  • 문제를 번역한 사람: sehun