당신은 지금 레트로 RPG게임을 하고 있다. 이 게임의 필드는 가로 100칸, 세로 100칸의 격자로 이루어져 있다. 이 필드의 왼쪽에서 x번째, 위에서 y번째에 위치한 칸을 (x, y) 라고 나타낸다. 당신이 조작하고 있는 캐릭터는 필드 내의 칸 위에만 위치할 수 있고, 필드 내를 상하좌우 한 칸씩 이동할 수 있다.
당신이 조작하고 있는 캐릭터는 지금 (X0, Y0) 에 위치하고 있고, 지금부터 N개의 목적지를 순서대로 방문할 예정이다. 여기서, 당신이 캐릭터를 조작할 때, 칸의 종류에 주의해서 이동해야 한다. 각 칸은 독이 있는 늪지대와 독이 없는 평지 중 하나이다. 캐릭터가 한 칸씩 이동할 때, 이동하려고 하는 칸이 늪지대일 경우 캐릭터는 대미지를 받고, 평지일 때는 대미지를 받지 않는다. 당신은 캐릭터가 받는 대미지를 줄이기 위해서, 적당한 경로를 골라 캐릭터가 대미지를 받는 횟수를 최소화하려고 한다. 이 때, 캐릭터는 이동 시에만 대미지를 받으며, 캐릭터가 대미지를 받는 기준은 이동하려고 하는 칸에 의해서만 결정된다는 것에 주의하라. 예를 들어, 지금 캐릭터가 늪지대에 위치하고 있고, 이동하려고 하는 칸이 평지라면 캐릭터는 대미지를 받지 않는다.
당신이 이 필드를 분석한 결과에 따르면, 왼쪽 위가 (A, B), 오른쪽 아래가 (C, D)인 직사각형에 포함된 칸은 평지이고, 나머지 칸은 모두 늪지대인 것으로 밝혀졌다. 캐릭터가 대미지를 받는 횟수를 최소화하면서 N개의 목적지를 순서대로 방문한다고 할 때, 캐릭터가 대미지를 받는 횟수를 구하시오.
ㅤ
입력
입력은 최대 50개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.
각 테스트 케이스는 N+3 줄로 이루어져 있다.
첫 번째 줄에는 목적지의 개수를 나타내는 정수 N (1 ≤ N ≤ 100) 이 주어진다.
두 번째 줄에는 직사각형 모양의 평지를 나타내는 정수 A,B,C,D (1 ≤ A ≤ C ≤ 100,1 ≤ B ≤ D ≤ 100) 가 주어진다. 캐릭터가 이동하려고 하는 칸 (x, y)가 A ≤ x ≤ C,B ≤ y ≤ D을 만족한다면 캐릭터는 대미지를 받지 않는다.
세 번째 줄에는 당신이 조작하려고 하는 캐릭터의 처음 위치를 나타내는 정수 X0, Y0 (1 ≤ X0, Y0 ≤ 100) 가 주어진다. 4번째 줄부터 N개의 줄에는 목적지의 좌표가 주어진다. 3+i 번째 줄에는 i번째 목적지를 나타내는 정수 Xi, Yi (1 ≤ Xi, Yi ≤ 100) 가 주어진다. 이 때, 캐릭터의 처음 위치 및 목적지의 좌표들은 모두 다르다. 즉, (Xj, Yj) ≠ (Xk, Yk)(0 ≤ j < k ≤ N) 을 만족한다.
입력의 마지막에는 0 하나가 주어진다.
ㅤ
출력
각 테스트 케이스의 답을 한 줄에 하나씩 출력한다.
ㅤ
ㅤ
힌트
(파란색 칸 : 늪지대, 갈색 칸 : 평지, ☺ : 캐릭터의 처음 위치, 숫자 : 목적지의 위치)
예제의 첫 번째 테스트 케이스는 위와 같이 나타낼 수 있다. (3, 3)부터 (5, 3)까지는 평지지만 (6, 3)과 (7, 3)은 늪지대이므로, 첫 번째 목적지를 방문할 때 대미지를 2번 받는다. 첫 번째 목적지부터 두 번째 목적지까지의 최단경로인 아래로 4칸 이동하게 되면, 이동 중의 모든 칸이 늪지대이기 때문에 대미지를 4번 받는다. 하지만 우회해서 평지를 거쳐 이동하게 되면, (6, 3), (6, 7), (7, 7)만 늪지대이기 때문에 대미지를 3번 받는다. 따라서, 대미지를 받는 횟수를 최소화하면서 이동하게 되면 대미지를 총 5번 받게 된다.
cinador 4년 전 2
문제
당신은 지금 레트로 RPG게임을 하고 있다. 이 게임의 필드는 가로 100칸, 세로 100칸의 격자로 이루어져 있다. 이 필드의 왼쪽에서 x번째, 위에서 y번째에 위치한 칸을 (x, y) 라고 나타낸다. 당신이 조작하고 있는 캐릭터는 필드 내의 칸 위에만 위치할 수 있고, 필드 내를 상하좌우 한 칸씩 이동할 수 있다.
당신이 조작하고 있는 캐릭터는 지금 (X0, Y0) 에 위치하고 있고, 지금부터 N개의 목적지를 순서대로 방문할 예정이다. 여기서, 당신이 캐릭터를 조작할 때, 칸의 종류에 주의해서 이동해야 한다. 각 칸은 독이 있는 늪지대와 독이 없는 평지 중 하나이다. 캐릭터가 한 칸씩 이동할 때, 이동하려고 하는 칸이 늪지대일 경우 캐릭터는 대미지를 받고, 평지일 때는 대미지를 받지 않는다. 당신은 캐릭터가 받는 대미지를 줄이기 위해서, 적당한 경로를 골라 캐릭터가 대미지를 받는 횟수를 최소화하려고 한다. 이 때, 캐릭터는 이동 시에만 대미지를 받으며, 캐릭터가 대미지를 받는 기준은 이동하려고 하는 칸에 의해서만 결정된다는 것에 주의하라. 예를 들어, 지금 캐릭터가 늪지대에 위치하고 있고, 이동하려고 하는 칸이 평지라면 캐릭터는 대미지를 받지 않는다.
당신이 이 필드를 분석한 결과에 따르면, 왼쪽 위가 (A, B), 오른쪽 아래가 (C, D)인 직사각형에 포함된 칸은 평지이고, 나머지 칸은 모두 늪지대인 것으로 밝혀졌다. 캐릭터가 대미지를 받는 횟수를 최소화하면서 N개의 목적지를 순서대로 방문한다고 할 때, 캐릭터가 대미지를 받는 횟수를 구하시오.
ㅤ
입력
입력은 최대 50개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.
각 테스트 케이스는 N+3 줄로 이루어져 있다.
첫 번째 줄에는 목적지의 개수를 나타내는 정수 N (1 ≤ N ≤ 100) 이 주어진다.
두 번째 줄에는 직사각형 모양의 평지를 나타내는 정수 A,B,C,D (1 ≤ A ≤ C ≤ 100,1 ≤ B ≤ D ≤ 100) 가 주어진다. 캐릭터가 이동하려고 하는 칸 (x, y) 가 A ≤ x ≤ C, B ≤ y ≤ D 을 만족한다면 캐릭터는 대미지를 받지 않는다.
세 번째 줄에는 당신이 조작하려고 하는 캐릭터의 처음 위치를 나타내는 정수 X0, Y0 (1 ≤ X0, Y0 ≤ 100) 가 주어진다. 4번째 줄부터 N개의 줄에는 목적지의 좌표가 주어진다. 3+i 번째 줄에는 i번째 목적지를 나타내는 정수 Xi, Yi (1 ≤ Xi, Yi ≤ 100) 가 주어진다. 이 때, 캐릭터의 처음 위치 및 목적지의 좌표들은 모두 다르다. 즉, (Xj, Yj) ≠ (Xk, Yk) (0 ≤ j < k ≤ N) 을 만족한다.
입력의 마지막에는 0 하나가 주어진다.
ㅤ
출력
각 테스트 케이스의 답을 한 줄에 하나씩 출력한다.
ㅤ
ㅤ
힌트
(파란색 칸 : 늪지대, 갈색 칸 : 평지, ☺ : 캐릭터의 처음 위치, 숫자 : 목적지의 위치)
예제의 첫 번째 테스트 케이스는 위와 같이 나타낼 수 있다. (3, 3)부터 (5, 3)까지는 평지지만 (6, 3)과 (7, 3)은 늪지대이므로, 첫 번째 목적지를 방문할 때 대미지를 2번 받는다. 첫 번째 목적지부터 두 번째 목적지까지의 최단경로인 아래로 4칸 이동하게 되면, 이동 중의 모든 칸이 늪지대이기 때문에 대미지를 4번 받는다. 하지만 우회해서 평지를 거쳐 이동하게 되면, (6, 3), (6, 7), (7, 7)만 늪지대이기 때문에 대미지를 3번 받는다. 따라서, 대미지를 받는 횟수를 최소화하면서 이동하게 되면 대미지를 총 5번 받게 된다.