알고리즘 : 2 차원 행렬 재정렬 (요소 '뒤집기'를 통해)

Question

알고리즘을 다음과 (효율적으로) 해결하는 것에 대해 궁금합니다. 숫자 [1..9]의 2D 행렬이 상단에서 수평선 1)에서 바닥 (9)까지 수직으로 또는 수평으로 다른 숫자로 뒤집기 만합니다.

예시 입력 행렬 :

1 8 2 6 1 6 
9 2 5 1 6 2 
3 6 9 2 9 8 
5 1 7 4 2 8 
4 2 7 6 9 5 

원하는 출력 매트릭스 '뒤집기'에

1 1 1 1 2 2 
2 2 2 2 3 4 
4 5 5 5 6 6 
6 6 6 7 7 8 
8 8 9 9 9 9 

명확화 : 예를 들면, 입력 행렬을 가지고. 왼쪽 상단에 "1"이 있습니다. 그 1은 그 옆에있는 8을 사용하여 수평으로 뒤집을 수 있습니다 (첫 번째 행은 이제 8 1 2 6 1 6이됩니다). 또는 아래의 9가 수직으로됩니다 (첫 번째 열은 이제 9 1 3 5 4이됩니다). 2를 대각선으로 뒤집을 수 없습니다.

이 문제의 해결책은 무엇입니까?

Answer 1

대각선으로 뒤집을 수없는 부분은 빨간 청어입니다. (바로 옆에있는 요소를 뒤집은 다음 그 아래에있는 요소를 뒤집기 만하면됩니다.) 따라서 임의의 요소는 반복되는 뒤집기에 의해 행렬의 다른 요소와 교환 될 수 있습니다. 이 추론을 계속하면 원하는 최종 상태가 오름차순으로 요소를 포함하고 왼쪽에서 오른쪽으로 그리고 위에서 아래로 증가하는 행렬임을 알 수 있습니다 (최종 상태 에서처럼).

이 최종 결과를 빠르게 생성하려면 2 차원 배열에서 평면 목록으로 초기 행렬을 바꾼다. 종류. 그런 다음 다시 2D 배열로 바꿉니다.

당신이 최종 결과를 생성 할 수있는 법적 움직임의 순서를 알 필요가있는 경우 (! 그런 순서가 하지 고유 있습니다), 다음과 같은 간단한 알고리즘을 할 것입니다 :에 의해

1. 시작 좌상 구석에 속하는 요소의 위치 지정; 이것이 현재 위치입니다.
2. 나머지 행렬에서 최소 요소를 찾습니다.
3. 이 요소를 현재 위치의 열에 도달 할 때까지 왼쪽으로 뒤집은 다음 현재 위치의 행에 도달 할 때까지 위쪽으로 대칭 이동합니다.
4. 현재 위치를 올바르게 배치했음을 표시하십시오.
5. 현재 위치를 하나의 색인으로 오른쪽으로 이동하여 다음 위치로 이동하거나 전체 행이 배치 된 경우 다음 행의 시작으로 이동합니다.
6. 전체 매트릭스가 위치 할 때까지 반복하십시오.

가장 효율적입니까? 있을 것 같지 않게. 간단하고 효과적인? 전혀.

Answer 2

멋진 퍼즐! 어쨌든 수정 된 버전의 정렬 알고리즘을 사용해 볼 수 있습니다. 구현에 너무 좋지는 않지만 나중에 하나를 줄 수 있습니다. 이를 해결하는 다른 방법은 A * 알고리즘을 이용하는 것입니다. 그것은 인공 지능에 사용 된 알고리즘을 찾는 경로이지만, 이와 비슷한 문제에 적용되는 것을 보았습니다.