728x90
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r,
www.acmicpc.net
문제에서 주어준대로 재귀로 풀면 되기 때문에 아주 쉽게 풀 수 있었다.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n, r, c;
int cnt = 0;
int result;
bool found = false;
void visit(int rowStart, int rowEnd, int colStart, int colEnd) {
if (found)
return;
if (rowEnd - rowStart == 1) {
if (++cnt && rowStart == r && colStart == c) {
result = cnt;
found = true;
return;
}
else if (++cnt && rowStart == r && colEnd == c) {
result = cnt;
found = true;
return;
}
else if (++cnt && rowEnd == r && colStart == c) {
result = cnt;
found = true;
return;
}
else if (++cnt && rowEnd == r && colEnd == c) {
result = cnt;
found = true;
return;
}
else {
return;
}
}
visit(rowStart, rowStart + (rowEnd + 1 - rowStart) / 2 - 1, colStart, colStart + (colEnd + 1 - colStart) / 2 - 1);
visit(rowStart, rowStart + (rowEnd + 1 - rowStart) / 2 - 1, colStart + (colEnd + 1 - colStart) / 2, colEnd);
visit(rowStart + (rowEnd + 1 - rowStart) / 2, rowEnd, colStart, colStart + (colEnd + 1 - colStart) / 2 - 1);
visit(rowStart + (rowEnd + 1 - rowStart) / 2, rowEnd, colStart + (colEnd + 1 - colStart) / 2, colEnd);
}
int main() {
cin >> n >> r >> c;
n = pow(2, n);
visit(0, n - 1, 0, n - 1);
cout << result - 1;
return 0;
}728x90
'알고리즘 문제' 카테고리의 다른 글
| [백준] 1476번 날짜 계산 (0) | 2020.03.23 |
|---|---|
| [백준] 1357번 뒤집힌 덧셈 (0) | 2020.03.23 |
| [백준] 11066번 파일 합치기 (0) | 2020.03.20 |
| [백준] 9325번 얼마? (0) | 2020.03.20 |
| [백준] 4539번 반올림 (0) | 2020.03.20 |