[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 꼬여있는 코일

• Given an 4n X 4n Matrix, where n is a positive integer taken as input. Imagine the matrix consisting of two interleaved coils whose centers are at the centre of the matrix. Implement a java program which takes an integer (n) as input and prints the two coils in two seperate lines.

Please have a look at the below examples to get a sense of what the two coils are :
• Example 1:
• Input: 1
• Matrix:

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16

• Output the Two Coils as:
– Coil1: 10 06 02 03 04 08 12 16
– Coil2: 07 11 15 14 13 09 05 01

 

Solution.

I can easily guess. there are some rules. the start point are always (2n, 2n+1) and (2n+1, 2n) and there are 4 directions which follow this order: UP, RIGHT, DOWN, LEFT. and  In (2n,2n+1)  case it starts from UP, and (2n+1, 2n), it starts from DOWN. so I can easily calculate next values.

 


#include <stdio.h>
#include <stdlib.h>

#define DIRECTION_NUMBER 4
#define STEP 2
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

void find_direction( int x, int y, int n, int direction ) {
 int end = n * n * 4 * 2;
 int step = STEP;
 int current_direction = direction;
 int pos_x = x;
 int pos_y = y;
 int delta = 0;
 int count = 1;

int seed = (y-1)*4*n+(x);
 printf("%d", seed);
 while( count < end ) {
 for( int i = 0; i < STEP; i++ ) {
 switch( direction ){
 case UP:
 delta = -(4*n);
 break;
 case RIGHT:
 delta = 1;
 break;
 case DOWN:
 delta = 4*n;
 break;
 case LEFT:
 delta = -1;
 break;


 }

for ( int j = 0; j < step && count < end; j++ ) {
 seed += delta;
 printf(" %d", seed, delta );
 count++;
 }

direction++;
 if( DIRECTION_NUMBER == direction ){
 direction = UP;
 }
 }
 step += STEP;
 }
 printf("\n");
}

int main( int argc, char *argv[] ){
 int n = atoi(argv[1]);
 find_direction( 2*n , 2*n+1, n, UP );
 find_direction( 2*n+1, 2*n , n, DOWN );
 return 0;
}