문제 번호 5032 --포상(Cow Treats)

5032: 포상(Cow Treats)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 2  해결 문제 수: 2
[제출][채점상황][게시판][:]

문제 설명

이차원 배열로 주어지는 데이터에서 가장 큰 수를 빠른 행 , 빠른 열 순으로 옮길 때 최종적으로 만들어지는 테이블의 상태를 구하는 문제.

단 , 두 수를 교환할 수는 없고 행,열 전체를 교환할 수 있고 놓은 수의 행,열은 더 이상 움직일 수 없다.

다음과 같은 3 * 4 행열이 주어질 때 교환이 이루어지는 알고리즘은 다음과 같다.

         5  7  4  1
         9 99  2  6
         8  3 10 11

가장 큰수를 찾는다. 99

2 행 2 열에 있는 99 를 1 행,1 열로 옮겨야 한다.

이 때 2 행과 1 행을 바꾸고 , 2 열과 1 열을 바꾸면

5 7 4 1         99  9  2  6 
9 99 2 6     ->  7  5  4  1
8 3 10 11        3  8 10 11

이제 1 행과 1 열은 건드릴수 없다.

다음으로 큰 수는 3 행 4 열에 있는 11. 이 수를 2 행 2 열로 옮겨야 한다.

2 열과 4 열을 바꾸고 , 2 행과 3 행을 바꾸면

99  9  2  6       99   6  2  9
 7  5  4  1   ->   3  11 10  8
 3  8 10 11        7   1  4  5

다음 큰 수 10 은 움직일 필요가 없고 ,

9 는 미리 했고 ,

8 은 움직일 필요가 없고 ,

7 은 움직일 필요가 없고

5 는 3 행 2 열에 옮기면 가장 좋으나 1 행 2 행은 얼어 붙었고 , 열은 모두 얼어붙어 나머지는 수는 움직일 방법이 없으므로 끝

입력

첫줄 공백으로 구분되는 W와 H가 입력(1 <= W <= 25, 1 <= H <= 25)

둘째 줄부터 H줄까지 W개의 각각의 데이터가 입력

출력

최종 배치를 출력한다.

입력예시

4 3
5 7 4 1
9 99 2 6
8 3 10 11

출력예시

99 6 2 9
3 11 10 8
7 1 4 5

도움말

출처

[제출][채점상황]