보석 동굴로 향하는 마법의 문은 다양한 보석으로 가득 찬 M X N 격자 형태입니다. 보석은 크게 세 종류로 나뉩니다: 다양한 색과 모양을 가진 일반 보석과, 특별한 두 종류의 보석 - 폭탄 보석과 비브라늄 보석입니다.
Match-3는 셋 이상의 동일한 일반 보석이 수직 또는 수평 방향으로 연속해 배열된 형태입니다. 하나의 보석이 서로 교차하는 수평 Match-3와 수직 Match-3 양쪽에 속해 있을 수도 있습니다. 폭탄 보석은 Match-3를 형성할 수 없습니다. 비브라늄 보석도 마찬가지입니다.
초기 상태에 격자에 Match-3는 존재하지 않습니다. 당신이 두 일반 보석을 손으로 만지면 둘의 위치가 교환이 됩니다. 한 번의 교환은 특정한 규칙에 의해 보석을 격자에서 사라지게 하는 연쇄 반응을 촉발할 수 있습니다.
최초 교환 이후, 아래의 과정이 더 이상 변화가 없을 때까지 격자에서 반복됩니다:
Phase 1 : Match-3 연쇄 반응
1. Match-3에 속하는 모든 보석이 동시에 사라집니다.
2. 사라진 보석 위에 있는 모든 보석이 중력에 의해 낙하해 빈 자리를 메웁니다. 이 과정에서 한 칸 이상 떨어지는 모든 폭탄 보석은 활성화됩니다.
3. 보석이 낙하하고 새롭게 Match-3이 형성될 경우, 이 Phase는 첫 번째 단계부터 반복됩니다.
4. 더 이상 Match-3이 형성되지 않는다면, Phase 2로 넘어갑니다.
Phase 2 : 활성 폭탄 폭파
1. 현재 시점에서 활성 상태에 있는 모든 폭탄은 동시에 폭발합니다.
2. 폭발한 각 폭탄은 수평과 수직 방향으로 광선을 방출합니다.
3. 광선은 폭탄의 위치에서 격자 테두리까지 뻗어 나갑니다.
4. 광선은 비브라늄 보석에 부딪히면 막힙니다.
5. 광선의 경로에 있는 모든 일반 보석과 폭탄은 폭발한 폭탄과 함께 사라집니다.
6. 아직 폭발하지 않은 폭탄도 광선에 맞으면 폭발하지 않고 사라집니다.
7. 사라진 보석 위에 있는 보석은 중력에 의해 떨어져 새로 생긴 빈 자리를 메웁니다. 이 과정에서 한 칸 이상 떨어지는 모든 폭탄은 활성화됩니다. 이후 Phase 1이 반복됩니다.
Phase 1과 Phase 2에서 아무런 변화가 일어나지 않는다면, 모든 과정은 종료됩니다. 폭탄 보석과 비브라늄 보석은 둘 다 최초 교환에서 선택되지 않으며 Match-3를 이루지도 않음에 유의합시다. 또한 비브라늄 보석은 절대 사라지지 않으며 폭탄 광선의 방패 역할만 수행하되, 중력의 영향을 받아 그 밑의 빈 공간으로는 떨어질 수 있음에 유의합시다.
예를 들어, 그림 1과 같은 6 X 4 격자 형태의 마법의 문을 생각해봅시다. 그림에서 0은 폭탄 보석, -1은 비브라늄 보석, 양수는 일반 보석을 나타냅니다. 그림 (a)와 같은 초기 상태에서 시작해서 (6, 1)과 (5, 4)에 있는 두 보석을 교환하면, 그림 (b)와 같은 상태가 됩니다. 위치 (r, c)는 위에서 r번째 행, 왼쪽에서 c번째 열을 의미합니다. 좌표는 1부터 시작합니다. 상태 (b)는 3개의 2로 이루어진 Match-3를 포함합니다. Phase 1에 의해 해당 보석이 사라지면 상태 (c)가 됩니다. 이 시점에서 (4, 3) 위치에 있는 폭탄 보석은 활성화되고 새롭게 3개의 1로 이루어진 Match-3가 형성됩니다. 다시 Phase 1에서 3개의 1이 제거되면 상태 (d)가 됩니다. 더 이상 Match-3가 없으므로 Phase 2에 의해 폭탄이 폭발합니다. 그 결과가 상태 (e)입니다. 이때, 3개의 1과 4개의 3으로 이루어진 두 Match-3가 있습니다. 또 다시 Phase 1에 의해 보석이 사라지면 상태 (f)가 됩니다. 이 상태에서는 더 이상 변화가 일어나지 않기에 해당 상태가 최종 상태가 됩니다. 총 18개의 보석이 이 과정에서 사라집니다.
<그림 1 참조>
마법의 문은 특정 수 이상 보석이 사라지면 열립니다. 당신은 마법의 문과 교환할 두 보석의 정보가 주어지면, 한 번의 교환으로 일어나는 연쇄 반응이 완전히 끝날 때까지 사라지는 보석의 개수를 계산하는 프로그램을 작성해야 합니다.
입력
프로그램은 표준 입력을 읽습니다. 입력은 격자의 행의 수와 열의 수를 나타내는 두 정수 m과 n으로 시작됩니다. (3 <= m, n <= 80). 다음 m개의 줄에 격자 각 행의 보석을 나타내는 n개의 정수가 들어오는데, 0은 폭탄 보석, -1은 비브라늄 보석, 1부터 9까지 정수는 일반 보석을 나타냅니다. 마지막 줄에는 네 정수 r1, c1, r2, c2가 들어오는데, 교환할 서로 다른 두 일반 보석의 좌표를 나타냅니다 (1 <= r1, r2 <= m; 1 <= c1, c2 <= n). 좌표는 1부터 시작됩니다.
출력
프로그램은 표준 출력을 출력합니다. 정확히 한 줄을 출력하세요. 줄은 모든 과정이 완료된 후 사라진 총 보석의 수를 나타내는 하나의 정수를 담고 있어야 합니다.
ez_code 9달 전 8
문제
보석 동굴로 향하는 마법의 문은 다양한 보석으로 가득 찬 M X N 격자 형태입니다. 보석은 크게 세 종류로 나뉩니다: 다양한 색과 모양을 가진 일반 보석과, 특별한 두 종류의 보석 - 폭탄 보석과 비브라늄 보석입니다.
Match-3는 셋 이상의 동일한 일반 보석이 수직 또는 수평 방향으로 연속해 배열된 형태입니다. 하나의 보석이 서로 교차하는 수평 Match-3와 수직 Match-3 양쪽에 속해 있을 수도 있습니다. 폭탄 보석은 Match-3를 형성할 수 없습니다. 비브라늄 보석도 마찬가지입니다.
초기 상태에 격자에 Match-3는 존재하지 않습니다. 당신이 두 일반 보석을 손으로 만지면 둘의 위치가 교환이 됩니다. 한 번의 교환은 특정한 규칙에 의해 보석을 격자에서 사라지게 하는 연쇄 반응을 촉발할 수 있습니다.
최초 교환 이후, 아래의 과정이 더 이상 변화가 없을 때까지 격자에서 반복됩니다:
Phase 1과 Phase 2에서 아무런 변화가 일어나지 않는다면, 모든 과정은 종료됩니다. 폭탄 보석과 비브라늄 보석은 둘 다 최초 교환에서 선택되지 않으며 Match-3를 이루지도 않음에 유의합시다. 또한 비브라늄 보석은 절대 사라지지 않으며 폭탄 광선의 방패 역할만 수행하되, 중력의 영향을 받아 그 밑의 빈 공간으로는 떨어질 수 있음에 유의합시다.
예를 들어, 그림 1과 같은 6 X 4 격자 형태의 마법의 문을 생각해봅시다. 그림에서 0은 폭탄 보석, -1은 비브라늄 보석, 양수는 일반 보석을 나타냅니다. 그림 (a)와 같은 초기 상태에서 시작해서 (6, 1)과 (5, 4)에 있는 두 보석을 교환하면, 그림 (b)와 같은 상태가 됩니다. 위치 (r, c)는 위에서 r번째 행, 왼쪽에서 c번째 열을 의미합니다. 좌표는 1부터 시작합니다. 상태 (b)는 3개의 2로 이루어진 Match-3를 포함합니다. Phase 1에 의해 해당 보석이 사라지면 상태 (c)가 됩니다. 이 시점에서 (4, 3) 위치에 있는 폭탄 보석은 활성화되고 새롭게 3개의 1로 이루어진 Match-3가 형성됩니다. 다시 Phase 1에서 3개의 1이 제거되면 상태 (d)가 됩니다. 더 이상 Match-3가 없으므로 Phase 2에 의해 폭탄이 폭발합니다. 그 결과가 상태 (e)입니다. 이때, 3개의 1과 4개의 3으로 이루어진 두 Match-3가 있습니다. 또 다시 Phase 1에 의해 보석이 사라지면 상태 (f)가 됩니다. 이 상태에서는 더 이상 변화가 일어나지 않기에 해당 상태가 최종 상태가 됩니다. 총 18개의 보석이 이 과정에서 사라집니다.
<그림 1 참조>
마법의 문은 특정 수 이상 보석이 사라지면 열립니다. 당신은 마법의 문과 교환할 두 보석의 정보가 주어지면, 한 번의 교환으로 일어나는 연쇄 반응이 완전히 끝날 때까지 사라지는 보석의 개수를 계산하는 프로그램을 작성해야 합니다.
입력
프로그램은 표준 입력을 읽습니다. 입력은 격자의 행의 수와 열의 수를 나타내는 두 정수 m과 n으로 시작됩니다. (3 <= m, n <= 80). 다음 m개의 줄에 격자 각 행의 보석을 나타내는 n개의 정수가 들어오는데, 0은 폭탄 보석, -1은 비브라늄 보석, 1부터 9까지 정수는 일반 보석을 나타냅니다. 마지막 줄에는 네 정수 r1, c1, r2, c2가 들어오는데, 교환할 서로 다른 두 일반 보석의 좌표를 나타냅니다 (1 <= r1, r2 <= m; 1 <= c1, c2 <= n). 좌표는 1부터 시작됩니다.
출력
프로그램은 표준 출력을 출력합니다. 정확히 한 줄을 출력하세요. 줄은 모든 과정이 완료된 후 사라진 총 보석의 수를 나타내는 하나의 정수를 담고 있어야 합니다.