ez_code   9달 전

문제

보석 동굴로 향하는 마법의 문은 다양한 보석으로 가득 찬 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부터 시작됩니다.

출력

프로그램은 표준 출력을 출력합니다. 정확히 한 줄을 출력하세요. 줄은 모든 과정이 완료된 후 사라진 총 보석의 수를 나타내는 하나의 정수를 담고 있어야 합니다.

park12010   7달 전

번역 GOAT

rickyhi   7달 전

정상화의 신

john3550   7달 전

대 ez_code

yeonjj517   7달 전

번역추

shoe   7달 전

번역 정상화 완료.

smile_again   7달 전

지언PT를 사용하는건 반칙

kkkuuuiii   7달 전

그저 대 지 언

댓글을 작성하려면 로그인해야 합니다.