Tasks Details
hard
1.
HilbertMaze
Find the shortest path between two fields in a Hilbert maze.
Task Score
100%
Correctness
100%
Performance
100%
A halfling is searching for treasure hidden in a maze in the dwarfs' mine. He has a map of the maze and would like to find the shortest path to the treasure.
The maze has a specific shape. It is placed on a square grid with M2 cells, where M = 2N+1+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.
The mazes of sizes N = 1 and N = 2 are presented in the pictures below:
A maze of size N is constructed recursively from the layout of the maze of size N−1 (like the Hilbert curve). It contains four mazes of size N−1, each maze in one quarter. The maze in the bottom-left quarter is rotated by 90 degrees clockwise and the maze in the bottom-right quarter is rotated by 90 degrees counter-clockwise. The mazes in the top quarters are not rotated. There are three additional rocks (squares marked in green in the picture below) in the areas where the mazes intersect. The construction of the maze of size N = 3 is shown below:
The halfling would like to reach the treasure in the smallest number of steps possible. At each step, he can move to any one of the four adjacent cells (north, south, west, east) that does not contain a rock and is not outside of the grid.
For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):
Write a function:
int solution(int N, int A, int B, int C, int D);
that, given the size of the maze N, coordinates of the halfling (A, B) and coordinates of the treasure (C, D), returns the minimum number of steps required for the halfling to reach the treasure.
Examples
Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.
Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:
Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2N+1];
- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C
Time spent on task 1 minutes
Notes
not defined yet
Code: 05:50:28 UTC,
c,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513
#include <stdio.h>
#include <stdlib.h>
int pow_two (int x) {
return (1 << x);
}
int abs (int x) {
return x < 0 ? 0 - x : x;
}
int min (int a, int b) {
return a < b ? a : b;
}
int solution (int N, int A, int B, int C, int D) {
int *start_xqueue, *start_yqueue, *end_xqueue, *end_yqueue;
int *block_index_queue, *block_direction_queue, *block_cen_xqueue, *block_cen_yqueue;
int left_border, up_border, right_border, down_border, hor_cen_line, ver_cen_line;
int start_size, end_size, block_size;
int temp_x, temp_y, tmpx, tmpy;
int start_idx, end_idx;
int result;
start_xqueue = (int*)malloc(sizeof(int) * (N << 1));//record x coordinate of points passed from start point
start_yqueue = (int*)malloc(sizeof(int) * (N << 1));
end_xqueue = (int*)malloc(sizeof(int) * (N << 1));
end_yqueue = (int*)malloc(sizeof(int) * (N << 1));//record y coordinate of points passed from end point
block_index_queue = (int*)malloc(sizeof(int) * N);//record index of blocks in the stack
block_direction_queue = (int*)malloc(sizeof(int) * N);//record directions of a block to upper block
block_cen_xqueue = (int*)malloc(sizeof(int) * N);//record x coordinate of center point of blocks in the stack
block_cen_yqueue = (int*)malloc(sizeof(int) * N);
start_size = 0;
end_size = 0;
block_size = 0;
block_index_queue[block_size] = N;//first block enqueue is the biggest block
block_direction_queue[block_size] = 0;//the original block is not rotated
block_cen_xqueue[block_size] = pow_two(N);
block_cen_yqueue[block_size++] = pow_two(N);
start_xqueue[start_size] = A;
start_yqueue[start_size++] = B;
while (block_size > 0) {//first record points passed from start point
ver_cen_line = block_cen_xqueue[--block_size];//vertical center line of this block
hor_cen_line = block_cen_yqueue[block_size];//horizontal center line of this bloc
left_border = ver_cen_line - pow_two(block_index_queue[block_size]);
right_border = (ver_cen_line << 1) - left_border;
up_border = hor_cen_line + pow_two(block_index_queue[block_size]);
down_border = (hor_cen_line << 1) - up_border;
temp_x = start_xqueue[start_size - 1];
temp_y = start_yqueue[start_size - 1];//retrieve the newest point in start queue and check how it can move in this block
if (temp_x == left_border || temp_x == right_border || temp_y == up_border || temp_y == down_border) {
continue;//if the point is on the border, we just leave it to move in upper blocks
}
if (block_direction_queue[block_size] < 0) {//the block is shifted 90 degrees clockwise
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//if the point is on center lines
if (temp_y != hor_cen_line) {//not the center point, we move it to center point and move it to nearest border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;//the border is determined by the direction of this block!
} else {//according to the direction of the block and some block examples, in this case we just need to move to the left border or right border
if (temp_x <= ver_cen_line) {//we can see this from block examples
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;
} else {
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
}
}
} else {//not on the center lines, on one of the our quadrants instead. we should leave it to be handled in lower/smaller blocks
block_size++;//do not forget
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//the second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//the second quadrant is upper in this block with left direction
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//the third quadrant is not rotated
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//the first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//the first quadrant is also left directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//the fourth quadrant
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (block_direction_queue[block_size] == 1) {//this block is rotated 90 degrees counter-clockwise
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//this point is on the center lines
if (temp_y != hor_cen_line) {//not on horizontal center line, should be moved to center point, then to right border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
} else {
if (temp_x >= ver_cen_line) {//move to right border
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
} else {//move to left border
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//up directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (!block_direction_queue[block_size]){//the block is of the original direction. i.e. not rotated
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//this point is on the center lines
if (temp_x != ver_cen_line) {//not on vertical center line. should be moved to center point then to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
} else {//on vertical center line
if (temp_y <= hor_cen_line) {//be moved to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
} else {//be moved to up border. can see this in example figures
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
}
}
} else {//in one of the four quadrants of this block
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//left directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else {//this block is of up direction
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//on the center lines
if (temp_x != ver_cen_line) {//not on vertical line. should be moved to center point, then to up border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
} else {
if (temp_y >= hor_cen_line) {//move to up border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
} else {//cannnot move to up border because of rock. should be moved to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
}
}
} else {//the point is in one of the four quadrants of this block
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//the second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//left directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//the third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//also the up directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//the fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//up directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
}
}
block_index_queue[block_size] = N;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = pow_two(N);
block_cen_yqueue[block_size++] = pow_two(N);
end_xqueue[end_size] = C;
end_yqueue[end_size++] = D;
while (block_size > 0) {//the same process for end point to record passed points
ver_cen_line = block_cen_xqueue[--block_size];
hor_cen_line = block_cen_yqueue[block_size];
left_border = ver_cen_line - pow_two(block_index_queue[block_size]);
right_border = (ver_cen_line << 1) - left_border;
up_border = hor_cen_line + pow_two(block_index_queue[block_size]);
down_border = (hor_cen_line << 1) - up_border;
temp_x = end_xqueue[end_size - 1];
temp_y = end_yqueue[end_size - 1];
if (temp_x == left_border || temp_x == right_border || temp_y == up_border || temp_y == down_border) {
continue;
}
if (block_direction_queue[block_size] < 0) {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_y != hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
if (temp_x <= ver_cen_line) {
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (block_direction_queue[block_size] == 1) {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_y != hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
if (temp_x >= ver_cen_line) {
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (!block_direction_queue[block_size]){
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_x != ver_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
} else {
if (temp_y <= hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
} else {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_x != ver_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
} else {
if (temp_y >= hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
} else {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
}
}
start_idx = start_size - 1;
end_idx = end_size - 1;
while (start_idx >= 0 && end_idx >= 0) {//delete all common points in start_queue and end_queue
if (start_xqueue[start_idx] == end_xqueue[end_idx] && start_yqueue[start_idx] == end_yqueue[end_idx]) {
start_idx--;
end_idx--;
if (start_idx < 0 || end_idx < 0) {//be careful. in case that all the start points are deleted (common) and only one point is left in end queue.
start_idx++;
end_idx++;
break;
}
} else {
break;
}
}
start_size = start_idx;
start_idx = 0;
end_size = end_idx;
end_idx = 0;
result = 0;
if (start_size < 0) {
if (end_size >= 0) {
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
while (end_size >= 0) {
result += abs (temp_x - end_xqueue[end_size]);
result += abs (temp_y - end_yqueue[end_size]);
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
} else {
temp_x = start_xqueue[start_idx];
temp_y = start_yqueue[start_idx++];
while (start_idx <= start_size) {
result += abs (temp_x - start_xqueue[start_idx]);
result += abs (temp_y - start_yqueue[start_idx]);
temp_x = start_xqueue[start_idx];
temp_y = start_yqueue[start_idx++];//be careful
}
if (end_size >= 0) {
left_border = 0;
right_border = pow_two(N + 1);
up_border = right_border;
down_border = 0;
tmpx = end_xqueue[end_size];
tmpy = end_yqueue[end_size];//the last point in start_queue and end_queue are both on borders of the original block
if (temp_x == left_border || temp_x == right_border) {
if (tmpx == temp_x || tmpy == up_border || tmpy == down_border) {//can use abs to directly calculate distance
result += abs (temp_x - tmpx) + abs (temp_y - tmpy);
} else {//two last points are in parallel borders
result += min (temp_y - down_border + tmpy - down_border, up_border - temp_y + up_border - tmpy) + right_border - left_border;
}
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
} else if (temp_y == up_border || temp_y == down_border) {
if (tmpy == temp_y || tmpx == left_border || tmpx == right_border) {
result += abs (temp_x - tmpx) + abs (temp_y - tmpy);
} else {//two last points are in parallel borders
result += min (temp_x - left_border + tmpx - left_border, right_border - temp_x + right_border - tmpx) + up_border - down_border;
}
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
while (end_size >= 0) {
result += abs (temp_x - end_xqueue[end_size]);
result += abs (temp_y - end_yqueue[end_size]);
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
free(start_xqueue);
free(start_yqueue);
free(end_xqueue);
free(end_yqueue);
free(block_index_queue);
free(block_direction_queue);
free(block_cen_xqueue);
free(block_cen_yqueue);
return result;
}
Analysis
Code: 05:50:33 UTC,
c,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513
#include <stdio.h>
#include <stdlib.h>
int pow_two (int x) {
return (1 << x);
}
int abs (int x) {
return x < 0 ? 0 - x : x;
}
int min (int a, int b) {
return a < b ? a : b;
}
int solution (int N, int A, int B, int C, int D) {
int *start_xqueue, *start_yqueue, *end_xqueue, *end_yqueue;
int *block_index_queue, *block_direction_queue, *block_cen_xqueue, *block_cen_yqueue;
int left_border, up_border, right_border, down_border, hor_cen_line, ver_cen_line;
int start_size, end_size, block_size;
int temp_x, temp_y, tmpx, tmpy;
int start_idx, end_idx;
int result;
start_xqueue = (int*)malloc(sizeof(int) * (N << 1));//record x coordinate of points passed from start point
start_yqueue = (int*)malloc(sizeof(int) * (N << 1));
end_xqueue = (int*)malloc(sizeof(int) * (N << 1));
end_yqueue = (int*)malloc(sizeof(int) * (N << 1));//record y coordinate of points passed from end point
block_index_queue = (int*)malloc(sizeof(int) * N);//record index of blocks in the stack
block_direction_queue = (int*)malloc(sizeof(int) * N);//record directions of a block to upper block
block_cen_xqueue = (int*)malloc(sizeof(int) * N);//record x coordinate of center point of blocks in the stack
block_cen_yqueue = (int*)malloc(sizeof(int) * N);
start_size = 0;
end_size = 0;
block_size = 0;
block_index_queue[block_size] = N;//first block enqueue is the biggest block
block_direction_queue[block_size] = 0;//the original block is not rotated
block_cen_xqueue[block_size] = pow_two(N);
block_cen_yqueue[block_size++] = pow_two(N);
start_xqueue[start_size] = A;
start_yqueue[start_size++] = B;
while (block_size > 0) {//first record points passed from start point
ver_cen_line = block_cen_xqueue[--block_size];//vertical center line of this block
hor_cen_line = block_cen_yqueue[block_size];//horizontal center line of this bloc
left_border = ver_cen_line - pow_two(block_index_queue[block_size]);
right_border = (ver_cen_line << 1) - left_border;
up_border = hor_cen_line + pow_two(block_index_queue[block_size]);
down_border = (hor_cen_line << 1) - up_border;
temp_x = start_xqueue[start_size - 1];
temp_y = start_yqueue[start_size - 1];//retrieve the newest point in start queue and check how it can move in this block
if (temp_x == left_border || temp_x == right_border || temp_y == up_border || temp_y == down_border) {
continue;//if the point is on the border, we just leave it to move in upper blocks
}
if (block_direction_queue[block_size] < 0) {//the block is shifted 90 degrees clockwise
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//if the point is on center lines
if (temp_y != hor_cen_line) {//not the center point, we move it to center point and move it to nearest border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;//the border is determined by the direction of this block!
} else {//according to the direction of the block and some block examples, in this case we just need to move to the left border or right border
if (temp_x <= ver_cen_line) {//we can see this from block examples
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;
} else {
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
}
}
} else {//not on the center lines, on one of the our quadrants instead. we should leave it to be handled in lower/smaller blocks
block_size++;//do not forget
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//the second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//the second quadrant is upper in this block with left direction
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//the third quadrant is not rotated
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//the first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//the first quadrant is also left directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//the fourth quadrant
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (block_direction_queue[block_size] == 1) {//this block is rotated 90 degrees counter-clockwise
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//this point is on the center lines
if (temp_y != hor_cen_line) {//not on horizontal center line, should be moved to center point, then to right border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
} else {
if (temp_x >= ver_cen_line) {//move to right border
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
} else {//move to left border
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//up directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (!block_direction_queue[block_size]){//the block is of the original direction. i.e. not rotated
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//this point is on the center lines
if (temp_x != ver_cen_line) {//not on vertical center line. should be moved to center point then to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
} else {//on vertical center line
if (temp_y <= hor_cen_line) {//be moved to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
} else {//be moved to up border. can see this in example figures
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
}
}
} else {//in one of the four quadrants of this block
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//left directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else {//this block is of up direction
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//on the center lines
if (temp_x != ver_cen_line) {//not on vertical line. should be moved to center point, then to up border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
} else {
if (temp_y >= hor_cen_line) {//move to up border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
} else {//cannnot move to up border because of rock. should be moved to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
}
}
} else {//the point is in one of the four quadrants of this block
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//the second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//left directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//the third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//also the up directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//the fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//up directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
}
}
block_index_queue[block_size] = N;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = pow_two(N);
block_cen_yqueue[block_size++] = pow_two(N);
end_xqueue[end_size] = C;
end_yqueue[end_size++] = D;
while (block_size > 0) {//the same process for end point to record passed points
ver_cen_line = block_cen_xqueue[--block_size];
hor_cen_line = block_cen_yqueue[block_size];
left_border = ver_cen_line - pow_two(block_index_queue[block_size]);
right_border = (ver_cen_line << 1) - left_border;
up_border = hor_cen_line + pow_two(block_index_queue[block_size]);
down_border = (hor_cen_line << 1) - up_border;
temp_x = end_xqueue[end_size - 1];
temp_y = end_yqueue[end_size - 1];
if (temp_x == left_border || temp_x == right_border || temp_y == up_border || temp_y == down_border) {
continue;
}
if (block_direction_queue[block_size] < 0) {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_y != hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
if (temp_x <= ver_cen_line) {
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (block_direction_queue[block_size] == 1) {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_y != hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
if (temp_x >= ver_cen_line) {
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (!block_direction_queue[block_size]){
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_x != ver_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
} else {
if (temp_y <= hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
} else {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_x != ver_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
} else {
if (temp_y >= hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
} else {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
}
}
start_idx = start_size - 1;
end_idx = end_size - 1;
while (start_idx >= 0 && end_idx >= 0) {//delete all common points in start_queue and end_queue
if (start_xqueue[start_idx] == end_xqueue[end_idx] && start_yqueue[start_idx] == end_yqueue[end_idx]) {
start_idx--;
end_idx--;
if (start_idx < 0 || end_idx < 0) {//be careful. in case that all the start points are deleted (common) and only one point is left in end queue.
start_idx++;
end_idx++;
break;
}
} else {
break;
}
}
start_size = start_idx;
start_idx = 0;
end_size = end_idx;
end_idx = 0;
result = 0;
if (start_size < 0) {
if (end_size >= 0) {
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
while (end_size >= 0) {
result += abs (temp_x - end_xqueue[end_size]);
result += abs (temp_y - end_yqueue[end_size]);
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
} else {
temp_x = start_xqueue[start_idx];
temp_y = start_yqueue[start_idx++];
while (start_idx <= start_size) {
result += abs (temp_x - start_xqueue[start_idx]);
result += abs (temp_y - start_yqueue[start_idx]);
temp_x = start_xqueue[start_idx];
temp_y = start_yqueue[start_idx++];//be careful
}
if (end_size >= 0) {
left_border = 0;
right_border = pow_two(N + 1);
up_border = right_border;
down_border = 0;
tmpx = end_xqueue[end_size];
tmpy = end_yqueue[end_size];//the last point in start_queue and end_queue are both on borders of the original block
if (temp_x == left_border || temp_x == right_border) {
if (tmpx == temp_x || tmpy == up_border || tmpy == down_border) {//can use abs to directly calculate distance
result += abs (temp_x - tmpx) + abs (temp_y - tmpy);
} else {//two last points are in parallel borders
result += min (temp_y - down_border + tmpy - down_border, up_border - temp_y + up_border - tmpy) + right_border - left_border;
}
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
} else if (temp_y == up_border || temp_y == down_border) {
if (tmpy == temp_y || tmpx == left_border || tmpx == right_border) {
result += abs (temp_x - tmpx) + abs (temp_y - tmpy);
} else {//two last points are in parallel borders
result += min (temp_x - left_border + tmpx - left_border, right_border - temp_x + right_border - tmpx) + up_border - down_border;
}
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
while (end_size >= 0) {
result += abs (temp_x - end_xqueue[end_size]);
result += abs (temp_y - end_yqueue[end_size]);
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
free(start_xqueue);
free(start_yqueue);
free(end_xqueue);
free(end_yqueue);
free(block_index_queue);
free(block_direction_queue);
free(block_cen_xqueue);
free(block_cen_yqueue);
return result;
}
Analysis
Code: 05:50:38 UTC,
c,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513
#include <stdio.h>
#include <stdlib.h>
int pow_two (int x) {
return (1 << x);
}
int abs (int x) {
return x < 0 ? 0 - x : x;
}
int min (int a, int b) {
return a < b ? a : b;
}
int solution (int N, int A, int B, int C, int D) {
int *start_xqueue, *start_yqueue, *end_xqueue, *end_yqueue;
int *block_index_queue, *block_direction_queue, *block_cen_xqueue, *block_cen_yqueue;
int left_border, up_border, right_border, down_border, hor_cen_line, ver_cen_line;
int start_size, end_size, block_size;
int temp_x, temp_y, tmpx, tmpy;
int start_idx, end_idx;
int result;
start_xqueue = (int*)malloc(sizeof(int) * (N << 1));//record x coordinate of points passed from start point
start_yqueue = (int*)malloc(sizeof(int) * (N << 1));
end_xqueue = (int*)malloc(sizeof(int) * (N << 1));
end_yqueue = (int*)malloc(sizeof(int) * (N << 1));//record y coordinate of points passed from end point
block_index_queue = (int*)malloc(sizeof(int) * N);//record index of blocks in the stack
block_direction_queue = (int*)malloc(sizeof(int) * N);//record directions of a block to upper block
block_cen_xqueue = (int*)malloc(sizeof(int) * N);//record x coordinate of center point of blocks in the stack
block_cen_yqueue = (int*)malloc(sizeof(int) * N);
start_size = 0;
end_size = 0;
block_size = 0;
block_index_queue[block_size] = N;//first block enqueue is the biggest block
block_direction_queue[block_size] = 0;//the original block is not rotated
block_cen_xqueue[block_size] = pow_two(N);
block_cen_yqueue[block_size++] = pow_two(N);
start_xqueue[start_size] = A;
start_yqueue[start_size++] = B;
while (block_size > 0) {//first record points passed from start point
ver_cen_line = block_cen_xqueue[--block_size];//vertical center line of this block
hor_cen_line = block_cen_yqueue[block_size];//horizontal center line of this bloc
left_border = ver_cen_line - pow_two(block_index_queue[block_size]);
right_border = (ver_cen_line << 1) - left_border;
up_border = hor_cen_line + pow_two(block_index_queue[block_size]);
down_border = (hor_cen_line << 1) - up_border;
temp_x = start_xqueue[start_size - 1];
temp_y = start_yqueue[start_size - 1];//retrieve the newest point in start queue and check how it can move in this block
if (temp_x == left_border || temp_x == right_border || temp_y == up_border || temp_y == down_border) {
continue;//if the point is on the border, we just leave it to move in upper blocks
}
if (block_direction_queue[block_size] < 0) {//the block is shifted 90 degrees clockwise
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//if the point is on center lines
if (temp_y != hor_cen_line) {//not the center point, we move it to center point and move it to nearest border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;//the border is determined by the direction of this block!
} else {//according to the direction of the block and some block examples, in this case we just need to move to the left border or right border
if (temp_x <= ver_cen_line) {//we can see this from block examples
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;
} else {
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
}
}
} else {//not on the center lines, on one of the our quadrants instead. we should leave it to be handled in lower/smaller blocks
block_size++;//do not forget
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//the second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//the second quadrant is upper in this block with left direction
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//the third quadrant is not rotated
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//the first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//the first quadrant is also left directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//the fourth quadrant
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (block_direction_queue[block_size] == 1) {//this block is rotated 90 degrees counter-clockwise
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//this point is on the center lines
if (temp_y != hor_cen_line) {//not on horizontal center line, should be moved to center point, then to right border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
} else {
if (temp_x >= ver_cen_line) {//move to right border
start_xqueue[start_size] = right_border;
start_yqueue[start_size++] = hor_cen_line;
} else {//move to left border
start_xqueue[start_size] = left_border;
start_yqueue[start_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//up directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (!block_direction_queue[block_size]){//the block is of the original direction. i.e. not rotated
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//this point is on the center lines
if (temp_x != ver_cen_line) {//not on vertical center line. should be moved to center point then to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
} else {//on vertical center line
if (temp_y <= hor_cen_line) {//be moved to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
} else {//be moved to up border. can see this in example figures
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
}
}
} else {//in one of the four quadrants of this block
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//left directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;//not rotated
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else {//this block is of up direction
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {//on the center lines
if (temp_x != ver_cen_line) {//not on vertical line. should be moved to center point, then to up border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = hor_cen_line;//be careful
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
} else {
if (temp_y >= hor_cen_line) {//move to up border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = up_border;
} else {//cannnot move to up border because of rock. should be moved to down border
start_xqueue[start_size] = ver_cen_line;
start_yqueue[start_size++] = down_border;
}
}
} else {//the point is in one of the four quadrants of this block
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {//the second quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;//left directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//the third quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//also the up directed
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {//first quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;//right directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {//the fourth quadrant
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;//up directed
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
}
}
block_index_queue[block_size] = N;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = pow_two(N);
block_cen_yqueue[block_size++] = pow_two(N);
end_xqueue[end_size] = C;
end_yqueue[end_size++] = D;
while (block_size > 0) {//the same process for end point to record passed points
ver_cen_line = block_cen_xqueue[--block_size];
hor_cen_line = block_cen_yqueue[block_size];
left_border = ver_cen_line - pow_two(block_index_queue[block_size]);
right_border = (ver_cen_line << 1) - left_border;
up_border = hor_cen_line + pow_two(block_index_queue[block_size]);
down_border = (hor_cen_line << 1) - up_border;
temp_x = end_xqueue[end_size - 1];
temp_y = end_yqueue[end_size - 1];
if (temp_x == left_border || temp_x == right_border || temp_y == up_border || temp_y == down_border) {
continue;
}
if (block_direction_queue[block_size] < 0) {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_y != hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
if (temp_x <= ver_cen_line) {
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (block_direction_queue[block_size] == 1) {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_y != hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
if (temp_x >= ver_cen_line) {
end_xqueue[end_size] = right_border;
end_yqueue[end_size++] = hor_cen_line;
} else {
end_xqueue[end_size] = left_border;
end_yqueue[end_size++] = hor_cen_line;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else if (!block_direction_queue[block_size]){
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_x != ver_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
} else {
if (temp_y <= hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
} else {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 0;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
} else {
if (temp_x == ver_cen_line || temp_y == hor_cen_line) {
if (temp_x != ver_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = hor_cen_line;//be careful
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
} else {
if (temp_y >= hor_cen_line) {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = up_border;
} else {
end_xqueue[end_size] = ver_cen_line;
end_yqueue[end_size++] = down_border;
}
}
} else {
block_size++;
if (temp_x < ver_cen_line) {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = -1;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (left_border + ver_cen_line) >> 1;
block_cen_yqueue[block_size++] = (down_border + hor_cen_line) >> 1;
}
} else {
if (temp_y > hor_cen_line) {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 1;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (up_border + hor_cen_line) >> 1;
} else {
block_index_queue[block_size] = block_index_queue[block_size - 1] - 1;
block_direction_queue[block_size] = 2;
block_cen_xqueue[block_size] = (ver_cen_line + right_border) >> 1;
block_cen_yqueue[block_size++] = (hor_cen_line + down_border) >> 1;
}
}
}
}
}
start_idx = start_size - 1;
end_idx = end_size - 1;
while (start_idx >= 0 && end_idx >= 0) {//delete all common points in start_queue and end_queue
if (start_xqueue[start_idx] == end_xqueue[end_idx] && start_yqueue[start_idx] == end_yqueue[end_idx]) {
start_idx--;
end_idx--;
if (start_idx < 0 || end_idx < 0) {//be careful. in case that all the start points are deleted (common) and only one point is left in end queue.
start_idx++;
end_idx++;
break;
}
} else {
break;
}
}
start_size = start_idx;
start_idx = 0;
end_size = end_idx;
end_idx = 0;
result = 0;
if (start_size < 0) {
if (end_size >= 0) {
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
while (end_size >= 0) {
result += abs (temp_x - end_xqueue[end_size]);
result += abs (temp_y - end_yqueue[end_size]);
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
} else {
temp_x = start_xqueue[start_idx];
temp_y = start_yqueue[start_idx++];
while (start_idx <= start_size) {
result += abs (temp_x - start_xqueue[start_idx]);
result += abs (temp_y - start_yqueue[start_idx]);
temp_x = start_xqueue[start_idx];
temp_y = start_yqueue[start_idx++];//be careful
}
if (end_size >= 0) {
left_border = 0;
right_border = pow_two(N + 1);
up_border = right_border;
down_border = 0;
tmpx = end_xqueue[end_size];
tmpy = end_yqueue[end_size];//the last point in start_queue and end_queue are both on borders of the original block
if (temp_x == left_border || temp_x == right_border) {
if (tmpx == temp_x || tmpy == up_border || tmpy == down_border) {//can use abs to directly calculate distance
result += abs (temp_x - tmpx) + abs (temp_y - tmpy);
} else {//two last points are in parallel borders
result += min (temp_y - down_border + tmpy - down_border, up_border - temp_y + up_border - tmpy) + right_border - left_border;
}
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
} else if (temp_y == up_border || temp_y == down_border) {
if (tmpy == temp_y || tmpx == left_border || tmpx == right_border) {
result += abs (temp_x - tmpx) + abs (temp_y - tmpy);
} else {//two last points are in parallel borders
result += min (temp_x - left_border + tmpx - left_border, right_border - temp_x + right_border - tmpx) + up_border - down_border;
}
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
while (end_size >= 0) {
result += abs (temp_x - end_xqueue[end_size]);
result += abs (temp_y - end_yqueue[end_size]);
temp_x = end_xqueue[end_size];
temp_y = end_yqueue[end_size--];
}
}
free(start_xqueue);
free(start_yqueue);
free(end_xqueue);
free(end_yqueue);
free(block_index_queue);
free(block_direction_queue);
free(block_cen_xqueue);
free(block_cen_yqueue);
return result;
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
4.
0.003 s
OK
5.
0.003 s
OK
6.
0.003 s
OK
7.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
4.
0.003 s
OK
5.
0.003 s
OK
6.
0.003 s
OK
7.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
4.
0.003 s
OK
5.
0.003 s
OK
6.
0.003 s
OK
7.
0.003 s
OK
8.
0.003 s
OK
9.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
4.
0.003 s
OK
5.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
4.
0.003 s
OK
5.
0.003 s
OK
6.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
expand all
Performance tests
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
4.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
1.
0.003 s
OK
2.
0.003 s
OK
3.
0.003 s
OK