탁구공과 쥐덫 (작은 입력)
면접 대비시간 제한5초메모리 제한512 MB
두 개의 고정된 변위 벡터가 주어질 때, 시작 트랩에서 연쇄 반응을 시뮬레이션하여 발동한 서로 다른 트랩의 수를 센다.
문제
큰 방 안에 쥐덫이 격자 모양으로 빽빽하게 놓여 있다. 쥐덫마다 탁구공 두 개가 올려져 있고, 덫이 튀면 두 공이 날아가 다른 쥐덫 위에 떨어져 그 덫까지 작동시킨다. 방의 벽은 끈적끈적해서 벽에 닿은 공은 그대로 붙어 버리고 아무 일도 일어나지 않는다.
모든 쥐덫은 두 공을 똑같은 방식으로 날린다. 공의 궤적은 자기를 날린 쥐덫에서 재는 X 변위와 Y 변위로 정해진다. 이제 탁구공 하나를 방 안으로 던진다. 그 공이 쥐덫 하나를 맞혀 작동시키고, 그 덫이 공 두 개를 날리고, 그 두 공이 다시 쥐덫 두 개를 작동시켜 네 공이 날아가는 식으로 연쇄가 이어진다. 연쇄가 멈추면 많은 쥐덫이 작동했지만 끝까지 공에 맞지 않은 덫도 남는다.
작동한 쥐덫이 몇 개인지 구하라.
쥐덫은 , 인 모든 격자점 (x, y)에 하나씩 놓여 있고 (0, 0)이 왼쪽 아래 덫이다. 이미 작동한 쥐덫에 공이 또 떨어져도 아무 일도 일어나지 않는다.
아래 그림은 너비 5, 높이 3인 방에서 두 공의 변위가 (-1, 0)과 (-1, -1)인 경우다. 처음 던진 공이 (4, 2)에 있는 쥐덫을 맞히면 최종적으로 쥐덫 12개가 작동한다.
입력
첫째 줄에 테스트 케이스의 수 가 주어진다. 각 테스트 케이스는 네 줄이다. 첫 줄에는 쥐덫 격자의 너비 와 높이 가 주어지고, 이 크기가 방의 크기와 같다. 다음 두 줄에는 두 공의 궤적이 X 변위와 Y 변위로 각각 주어진다. 예를 들어 그 두 줄이 0 1과 1 1이면, 작동한 쥐덫은 바로 위 덫으로 공 하나를 날리고 오른쪽 위 대각선 덫으로 공 하나를 날린다. 마지막 줄에는 처음 던진 공이 맞히는 쥐덫의 열과 행이 정수 두 개로 주어진다. 0 0은 왼쪽 아래 덫이다.
제한
- 각 변위는 이상 이하
- 두 변위 벡터 모두 이 아니다
- 열은 이상 이하, 행은 이상 이하
출력
각 테스트 케이스마다 Case #A: B 형식으로 한 줄씩 출력한다. 는 1부터 시작하는 테스트 케이스 번호이고, 는 작동한 쥐덫의 개수로 처음 작동한 덫도 포함한다.