경계선 검출

시간 제한1초메모리 제한128 MB

요약
이미지를 런렝스 부호화된 구간으로 주어질 때, 각 출력 화소를 주변 8개 화소와의 절댓값 차 중 최댓값으로 정하고 그 결과를 다시 구간으로 출력한다.
난이도

어려움10점 중 8점

유형
시뮬레이션, 구현, 구간, 배열
정답자
아직 제출이 없습니다

문제

어느 위성 영상 회사는 매우 큰 이미지를 런 렝스 부호화(RLE)로 기록하고 저장한다. 압축된 이미지를 읽어 아래에 설명하는 방식으로 경계선을 검출한 뒤, 검출된 경계선 이미지를 다시 압축하여 출력하는 프로그램을 작성하라.

간단한 경계선 검출 알고리즘은 각 출력 픽셀의 값을, 입력 이미지에서 그 픽셀과 이웃한 모든 픽셀들과의 차이의 절댓값 중 최댓값으로 정한다. 아래 입력 이미지를 살펴보자.

15151515100100100
100100100100100100100
1001001001001002525
1751752525252525
1751752525252525

입력 이미지

858585858500
85858585857575
75757575757575
751501507575750
01501500000

출력 이미지

출력 이미지의 왼쪽 위 픽셀은 ∣15−15∣|15-15|, ∣15−100∣|15-100|, ∣15−100∣|15-100| 중 최댓값이므로 8585이다.

4번째 행, 2번째 열의 픽셀은 ∣175−100∣|175-100|, ∣175−100∣|175-100|, ∣175−100∣|175-100|, ∣175−175∣|175-175|, ∣175−25∣|175-25|, ∣175−175∣|175-175|, ∣175−175∣|175-175|, ∣175−25∣|175-25| 중 최댓값이므로 150150이다.

모든 이미지는 22개 이상 10910^9개 이하의 픽셀을 가진다. 모든 이미지는 런 렝스 부호화(RLE)로 인코딩되며, 이는 픽셀 값(00-255255)과 반복 길이(11-10910^9)로 이루어진 쌍들의 나열이다. 하나의 입력 이미지는 최대 1,0001{,}000개의 쌍으로 이루어진다. 서로 이웃한 쌍은 항상 픽셀 값이 다르다. 이미지의 모든 행은 같은 수의 픽셀을 가진다.

입력

입력은 하나 이상의 이미지 정보로 이루어진다. 각 이미지는 한 행에 들어가는 픽셀 수, 즉 너비가 한 줄에 먼저 주어진다. 그 뒤로 RLE 쌍들이 한 줄에 하나씩 (값 반복길이) 주어진다. 0 0으로 이루어진 줄은 해당 이미지 데이터의 끝을 나타낸다. 너비가 0인 줄은 더 이상 처리할 이미지가 없음을 뜻한다.

출력

각 이미지에 대해, 주어진 순서대로 경계선 검출 결과를 입력 이미지와 같은 형식으로 출력한다. 먼저 이미지 너비를 한 줄에 출력하고, 이어서 RLE 쌍들을 (값 반복길이) 한 줄에 하나씩 출력한 뒤, 마지막에 0 0 줄을 출력한다. 결과에는 1,0001{,}000개를 넘는 RLE 쌍이 포함될 수 있다. 맨 끝에 너비가 0인 줄은 출력하지 않는다.

힌트

모든 픽셀 각각에 대해 출력 값을 계산하는 완전 탐색 방식은 시간 또는 메모리 제한을 초과할 가능성이 높다.

예제4

  1. 예제 1

    입력
    7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0
    예상 출력
    7
85 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
10
0 499999990
165 20
0 499999990
0 0
3
245 9
0 0

  2. 예제 2

    입력
    3
50 6
0 0
0
    예상 출력
    3
0 6
0 0

  3. 예제 3

    입력
    2
10 1
20 1
30 1
40 1
0 0
0
    예상 출력
    2
30 1
20 2
30 1
0 0

  4. 예제 4

    입력
    4
1 6
9 6
0 0
0
    예상 출력
    4
0 1
8 10
0 1
0 0