나선형 채우기
실버 V의견: 0
\(N \times M\) 크기의 격자가 있다. 이 격자의 모든 칸을 \(1\)부터 \(N \times M\)까지의 수로 채우려고 한다. 채우는 순서는 왼쪽 위 칸에서 시작하여 시계 방향 나선(소용돌이) 모양으로 진행한다. 즉, 처음에는 오른쪽으로 이동하면서 채우다가 격자의 경계나 이미 채워진 칸을 만나면 시계 방향(오른쪽 → 아래 → 왼쪽 → 위)으로 방향을 틀어 계속 채운다.
예를 들어 \(N = M = 3\)인 경우 격자는 다음과 같이 채워진다.
1 2 3
8 9 4
7 6 5
격자를 모두 채운 뒤, \(Q\)개의 질의가 주어진다. 각 질의는 행 번호 \(r\)와 열 번호 \(c\)로 이루어지며, 그 칸에 적힌 수가 무엇인지 답해야 한다. 행은 위에서부터, 열은 왼쪽에서부터 \(1\)번부터 센다.
\(1 \le N, M \le 2{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le r \le N\), \(1 \le c \le M\)
첫째 줄에 세 정수 \(N\), \(M\), \(Q\)가 공백으로 구분되어 주어진다 (\(1 \le N, M \le 2{,}000\), \(1 \le Q \le 100{,}000\)).
다음 \(Q\)개의 줄에 각각 두 정수 \(r\), \(c\)가 주어진다 (\(1 \le r \le N\), \(1 \le c \le M\)).
\(Q\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 질의가 가리키는 칸 \((r, c)\)에 적힌 수를 출력한다.
3 3 4
1 1
2 2
3 1
2 3
1
9
7
4
3x3 격자를 시계 방향 나선으로 채우면 다음과 같다.
1 2 3
8 9 4
7 6 5
(1,1)=1, (2,2)=9, (3,1)=7, (2,3)=4
2 4 3
1 4
2 1
2 4
4
8
5
2x4 격자를 시계 방향 나선으로 채우면 다음과 같다.
1 2 3 4
8 7 6 5
(1,4)=4, (2,1)=8, (2,4)=5
riseoj 작성
출처 Original
평가 및 의견
나선형 채우기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
나선형 채우기