50127. Connect the Numbers

I'm a slow walker, but I never walk backwards.

Task Description

We have a two-dimensional $N$ by $N$ array $A$ where every cell has a distinct integer from $0$ to $N^{2} – 1$. Also we have a two-dimensional $N$ by $N$ array $B$ where each cell has a pointer to an integer. Now we need to connect the numbers of array $A$ with the pointers in $B$. That is, if a cell of $A$ has the integer $i$, then its corresponding cell in $B$ should point to a cell in $A$ that as $i + 1$. To make the linkage well defined, if a cell of $A$ has the integer $N^2-1$, then its corresponding cell $B$ should point to a cell in $B$ that as $0$.

We illustrate this linkage by the following figure. $A\lbrack 2]\lbrack 0]$ is $0$ and $A\lbrack 1]\lbrack 2]$ is $1$, so $B\lbrack 2]\lbrack 0]$ should point to $A\lbrack 1]\lbrack 2]$. Now $A\lbrack 0]\lbrack 0]$ is $2$, so $B\lbrack 1]\lbrack 2]$ should pointe to $A\lbrack 0]\lbrack 0]$, and so on. Finally, Since $A\lbrack 2]\lbrack 2]$ is $8$ and $A\lbrack 2]\lbrack 0]$ is $0$, $B\lbrack 2]\lbrack 2]$ should point to $A\lbrack 2]\lbrack 0]$.

figurefigure

You need to write a function constructPointerArray, that given array $A$ and $B$, fill the values of element in $B$. The prototype of constructPointerArray function is as follows. Note that you cannot chanage the elements in A. You can change the elements in B, but not the value they point to.

void constructPointerArray(const int A[1024][1024], const int *B[1024][1024], int N);

The constructPointerArray.h is as follow.

#ifndef CONSTRUCT
#define CONSTRUCT
#define MAXN 1024
void constructPointerArray(const int A[MAXN][MAXN], const int *B[MAXN][MAXN]
, int N);
#endif

You may use the following main function to test your function.

#include <stdio.h>
#include "constructPointerArray.h"
int A[MAXN][MAXN];
const int *B[MAXN][MAXN];
int main()
{
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &A[i][j]);
        }
    }
    constructPointerArray(A, B, N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d%c", *B[i][j], j == N - 1 ? '\n' : ' ');
        }
    }
    return 0;
}

Input Format

The input contains only one test case. The first line contains one integer $N$, representing the size of array $A$. Each of the following $N$ lines contains $N$ integers, representing the elements of array $A$.

  • $N \leq 1024$

Output Format

Print the number pointed to by pointer array $B$. Note that we will also check the value of B to be within the address of A, no only the values pointed by B.

Subtasks

  • 40 points: $2 \leq N \leq 100$
  • 60 points: $101 \leq N \leq 1024$. You will get TLE if your algorithm is too slow.

Sample Input 1

3
2 4 7
3 6 1
0 5 8

Sample Output 1

3 5 8
4 7 2
1 6 0

Sample Input 2

4
6 2 5 14
11 1 15 9
3 0 13 4
7 8 12 10

Sample Output 2

7 3 6 15
12 2 0 10
4 1 14 5
8 9 13 11

Sample Input 3

5
0 15 10 21 13
22 17 16 2 23
3 18 8 5 20
14 4 7 1 24
19 11 6 12 9

Sample Output 3

1 16 11 22 14
23 18 17 3 24
4 19 9 6 21
15 5 8 2 0
20 12 7 13 10

Compile

gcc -std=c99 -O2 -c main.c
gcc -std=c99 -O2 -c constructPointerArray.c
gcc -std=c99 -O2 constructPointerArray.o main.o

Hint

For subtask 2 it would be time consuming to find the location of a particular number $i+1$ within $A$. You can use another array $D$ where $D\lbrack i]$ stores the address of $i$ in A. Then we can fill the array $D$ after scanning $A$, and fill the $B$ by pass through $D$.

Discussion