[C/C++] BOJ #1074 - Z

This problem involves the concept of self-replication.

The large shape forms a Z pattern, and the smaller shapes within also form Z patterns. The task is to find the number at a given row and column when the array is filled according to this Z-pattern structure.

Z of 2x2

If the array is 2x2, the numbers are arranged in a Z pattern as shown in the diagram. As the size increases, the pattern becomes more complex, as illustrated below.

Z of 8x8

You need to determine the number at a specific cell of this pattern.

---

Using recursive function calls to fill the array is the simplest solution. Since N is at most 15, the total number of cells is \(2^{2N} = 2^{30} = 1,073,741,824\), so it’s on the edge of being solvable within the 2-second time limit.

However, I solved this problem without recursion. Instead, I determined which part of the current square the (r, c) position belongs to.

For example, in an 8x8 array, if the target cell is (6, 3), you can repeatedly divide the r and c values by 2 to narrow down the section and calculate the number accordingly.

find (6, 3) at 8x8

As you progress, you increment the number based on the quadrant in which the current cell lies.

---

Hero Z

Here is the code I wrote. You can refer to it for reference.

//----------------------------------------------------------
//    baekjoon #1074 - Z
//        - by Aubrey Choi
//        - created at 2019-07-03
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, r, c, v = 0;
    scanf("%d%d%d", &n, &r, &c);
    for(int s = 0; r || c; s += 2, r>>=1, c>>=1)
    {
        v |= ((c & 1) + ((r & 1) << 1)) << s;
    }
    printf("%d\n", v);
    return 0;
}