시간제한 7초
문제
민건이는 원룸 청소하기 너무 귀찮아서 로봇청소기를 하나 구매했다. 로봇 청소기는 원룸 바닥을 돌아다니며, 열심히 바닥에 있는 먼지를 청소한다. 돈이 없는 민건이는 값싼 로봇 청소기를 구매하였다. 해당 로봇 청소기는 원룸 구조를 파악하여 똑똑하게 움직이는 것이 아닌 그냥 벽에 부딪히면 튕겨나온 방향으로 움직이는 무식한(?) 청소기이다. 벽이나 구조물을 만나기 전까지 계속해서 직진만 하며, 벽에 부딪히는 순간 방향을 틀어서 움직인다. 예를 들어, 벽이나 구조물에 부딪히면 다음과 같이 직각 혹은 반대 방향으로 움직인다.
[그림 1]
구조물은 회전이 가능하며, 현재
[그림 1]의 왼편에 나오는 구조물의 번호는 1번이다. 해당 구조물을 시계 방향으로 90° 회전시킬시 2번, 180° - 3번, 270° - 4번, 360° 는 구조물 1번과 동일하므로 1번이다. [그림 1]의 오른편에 나오는 구조물은 5번으로 붙혔다. 그림으로 표현하면 다음과 같다.
[그림 2]
무식한(?) 청소기답게 현재 높이보다 낮은 턱에 빠지면 더 이상 움직일 수 없어서 꺼내줘야한다. 낮은 턱의 경우 집 구조 상 어디든 존재하고 원룸 구조도에 “-1”로 표기한다. 또한 특이하게 다른 원룸과 달리 바닥에 5개의 워프 장치가 있는데, 워프 장치 한 쪽으로 갈 경우 다른 한 쪽으로 이동하게 된다.(그래서 바닥에 물건을 떨어뜨리면 찾기가 쉽지않다.) 이때 워프 장치를 통과한 후 진행방향은 워프 진입 직전의 진행 방향과 동일하다. 워프 장치는 번호는 6번부터 10번까지 존재하고, 원룸 구조도에 무조건 한 쌍으로 표기되어있다.
[그림 3]
[그림 4]
[그림 5]
[그림 6]
[그림 7][그림 4] 와 같은 원룸 구조도가 주어졌을 때, 로봇청소기의 이동 사례를 살펴보면 다음과 같다. [그림 5] 의 경우 시작지점으로 다시 돌아와서 이동이 종료되었고, [그림 6] 의 경우 낮은 턱에 빠져버려서 이동이 종료되었다. [그림 7] 의 경우 벽에 부딪혀 튕겨져나와, [그림 5] 와 동일하게 시작지점으로 돌아와서 이동이 종료되었다. [그림 5] 의 이동한 칸의 수는 6 이고, [그림 6] 의 이동한 칸의 수는 10 이다. [그림 7] 의 이동한 칸의 수는 4 이다. 시작 위치는 구조물, 워프 장치, 낮은 턱이 될 수 없다. 그 이외의 모든 공간에서는 시작할 수 있다.
원룸 구조는 N x N m2 이며, 로봇 청소기는 한 번에 한 칸씩 움직일 수 있다. 다시 말하면, 1m2 씩 움직일 수 있다. 로봇 청소기가 출발한 위치에 다시 돌아오면 작동을 멈춘다. 혹은 청소 진행 도중에 낮은 턱에 빠져버릴 경우 그대로 작동을 중지한다. 현재 민건이는 로봇청소기가 얼마나 열심히 일하는지 알고싶다. 원룸 구조도가 주어지고, 로봇 청소기가 임의의 위치에서 임의의 방향을 보고 이동을 시작하여, 끝나기까지 한 번이라도 지나간 칸의 수를 D 라고 하였을 때, D 의 최댓값을 구해보자!
입력
첫 번째 줄에 테스트 케이스의 개수 T(5 ≤ T ≤ 50) 가 주어진다. 각 테스트 케이스의 첫째 줄에 N(5 ≤ N ≤ 100) 이 주어지고, N 개의 줄에 걸쳐 N 개의 숫자가 공백을 통해 구분하여 입력된다. 각각의 입력되는 숫자는 -1 부터 10까지의 정수이다. 워프 장치는 최대 5쌍 존재한다. 낮은 턱은 최대 5개 존재할 수 있으며, 최소 1개 존재한다.
출력
각 테스트 케이스에 해당하는 결과값을 “#t result” 포맷으로 출력한다. (t는 1부터 T까지의 정수이다)
예제 입력
3
5
0 4 0 0 0
0 0 3 6 0
0 2 0 0 5
0 0 -1 0 0
0 6 0 1 0
8
0 0 1 1 0 0 0 4
0 0 0 0 0 0 5 0
0 0 0 3 0 0 0 0
2 0 0 4 3 4 0 0
0 0 0 0 0 0 0 0
0 0 2 0 0 5 0 0
0 0 5 0 3 0 0 0
0 0 4 0 0 3 1 0
4
1 1 1 1
1 1 -1 1
1 -1 0 -1
1 1 -1 1예제 출력
#1 10
#2 11
#3 1
댓글 없음:
댓글 쓰기