구슬게임 > 문제은행



문제은행

1383 : 구슬게임

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 0 회    시도횟수: 1 회   



구슬 게임은 여러 개의 구슬을 올려져있는 말판에서 하는 게임이다. 당신은 말판 위에서 로봇을 이용하여 최대한 많은 개수의 구슬을 얻어야 한다.

 

말판은 작은 사각형 칸이 여러개 모여 있는 직사각형 형태로 이루어져 있으며(따라서 각 행의 칸 개수와, 각 열의 칸 개수는 동일하다.), 격자는 숫자 '0~9', '#', 'U', 혹은 'L'로 이루어져 있으며, 숫자가 들어가 있는 경우 해당 칸에 들어 있는 구슬의 개수를 뜻하고, 숫자가 들어가 있지 않으면 그 칸에는 구슬이 존재 하지 않는다.

 

로봇은 처음에 맨 위, 맨 왼쪽의 칸부터 움직이기 시작한다. 로봇은 다음과 같은 규칙에 따라 움직인다.

규칙 :  

  • 로봇은 말판 밖으로 나갈 수 없다.
  • 로봇은 '#'표시가 된 칸으로 이동할 수 없다.
  • 로봇은 한 번에 오른쪽 칸이나 아래 칸으로 이동 할 수 있다.
  • 로봇은 'U'표시가 있는 칸에선 위로 이동 할 수 있다.
  • 로봇은 'L'표시가 있는 칸에선 왼쪽으로 이동 할 수 있다.

 

처음에 로봇이 임의의 칸에 들어갔을 때, 칸에 있는 모든 구슬을 가지게 된다. 이동을 하다 구슬이 차있지 않은 칸에 도착하게 되면 게임이 끝나게 된다(L이나 U의 경우 에는 지나쳐도 된다.)

 

로봇이 최대 몇 개의 구슬을 얻을 수 있는지 알아보는 프로그램을 작성하라.

 




첫 번째 줄에는 말판의 행과 열을 뜻하는 N, M(1≤N, M≤20)이 공백을 사이에 두고 입력된다. 그 다음 N개의 줄에는 각각 M개의 문자로 해당행의 말판의 정보가 입력되며, 숫자 '0'~'9', '#', 'U', 'L'의 글자의 조합으로 입력된다.

입력의 두 번째 줄의 첫 번째 글자, 다시 말해서 로봇이 시작하는 위치에 '#'가 들어오는 경우는 존재하지 않는다.



주어진 말판에 대해서 얻을 수 있는 최대 구슬의 개수를 출력한다.


2 3 
264 
3LL
15


5 5
8U4L9
0183U
U8#38
2158#
L65U7
44


최적의 경로는 오른쪽  오른쪽  아래  왼쪽 그리고 왼쪽이다.






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.