Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于AC了! 共享出来,希望大家一起指正!#include <stdio.h> #include <stdlib.h> #include <string.h> //#define DEBUG #define MAX_RLE_PAIRS 1000 #define FREE_LIST(elem,TYPE) do {\ TYPE *next = NULL;\ TYPE *element = (elem);\ while(element)\ {\ next = element->next;\ free(element);\ element = next;\ }\ } while(0) #ifndef max #define max(a, b) ((a)>(b)?(a):(b)) #endif #ifndef abs #define abs(a) ((a)>0?(a):-(a)) #endif typedef struct _Point { struct _Point *next; //Single Linked-List int color; int x; int y; } Point; typedef struct _H_Line { struct _H_Line *next; //Single Linked-List int color; int x; int y; int length; } H_Line; typedef struct _RLE_Line { struct _RLE_Line *next; //Single Linked-List int color; int length; } RLE_Line; typedef struct { RLE_Line *rle_lines; int rle_line_size; int width; } RLE_Image; //store all infomation about RUN-LENGTH-ENCODING typedef struct { H_Line **h_lines; int h_line_size; int width; int height; } Image; //store all invalid lines void print_RLE_image(const RLE_Image *rle_image) { RLE_Line *rle_line; printf("%d\n", rle_image->width); rle_line = rle_image->rle_lines; while(rle_line) { printf("%d %d\n", rle_line->color, rle_line->length); rle_line = rle_line->next; } printf("0 0\n"); } void print_image(const Image *image) { int i; H_Line *line; printf("\nBegin Image: \n"); printf(" Width=%d, Height=%d\n", image->width, image->height); for (i=0; i<image->h_line_size; i++) { printf(" %d-LINEs:\n", i+1); line = image->h_lines[i]; while(line) { printf(" (color=%d, x=%d, y=%d, length=%d)\n", line->color, line->x, line->y, line->length); line = line->next; } } printf("End Image\n"); } void print_points(Point *points) { Point *point = points; printf("Points: \n"); while(point) { printf(" (color=%d, x=%d, y=%d)\n", point->color, point->x, point->y); point = point->next; } } int build_rle_image(RLE_Image *rle_image) { int width; RLE_Line *rle_line; RLE_Line *tail; int color, length; scanf("%d", &width); if (!width) //end of the input { return -1; } //initialize rle_image->rle_lines = NULL; rle_image->rle_line_size = 0; rle_image->width = width; tail = NULL; while(1) { scanf("%d %d", &color, &length); if (!color && !length) { break; } rle_line = (RLE_Line *)malloc(sizeof(RLE_Line)); rle_line->next = NULL; rle_line->color = color; rle_line->length = length; if (tail == NULL) //first RLE line { rle_image->rle_lines = rle_line; tail = rle_line; } else { tail->next = rle_line; //insert new RLE line tail = rle_line; } rle_image->rle_line_size++; } return 0; } static void add_new_line_to_h_lines(Image *image, const RLE_Line *rle_line, int total_pix_size, H_Line **g_tail) { H_Line *h_line = NULL; H_Line **tail = g_tail; int cur_line_len_left = rle_line->length; int counter = 0; int t_total_pix_size = total_pix_size; // cur_line_len_left > 0, then should copy one more line firstly while (cur_line_len_left > 0) { counter++; h_line = (H_Line *)malloc(sizeof(H_Line)); h_line->next = NULL; h_line->color = rle_line->color; h_line->x = t_total_pix_size % image->width + 1; h_line->y = t_total_pix_size / image->width + 1; h_line->length = (cur_line_len_left + h_line->x - 1) > image->width ? (image->width - h_line->x + 1) : cur_line_len_left; cur_line_len_left -= h_line->length; if (counter == 2 && cur_line_len_left > image->width) { cur_line_len_left = (total_pix_size + rle_line->length)%image->width; if (cur_line_len_left == 0) { cur_line_len_left += image->width; } cur_line_len_left += image->width; //update current remained RLE-length t_total_pix_size = (total_pix_size + rle_line->length) - cur_line_len_left; //update total pixes } else { t_total_pix_size += h_line->length; } if (h_line->x == 1) //new line { tail = &image->h_lines[image->h_line_size++]; } if (*tail == NULL) { *tail = h_line; } else { (*tail)->next = h_line; *tail = h_line; } } *g_tail = *tail; } void build_image(const RLE_Image *rle_image, Image *image) { int total_pix_size = 0; RLE_Line *rle_line = NULL; H_Line *h_line = NULL, *g_tail=NULL; //initailize image->h_lines = (H_Line **)malloc(3 * MAX_RLE_PAIRS * sizeof(H_Line *)); memset(image->h_lines, 0, 3 * MAX_RLE_PAIRS * sizeof(H_Line *)); image->h_line_size = 0; image->width = rle_image->width; rle_line = rle_image->rle_lines; g_tail = image->h_lines[0]; while(rle_line) { add_new_line_to_h_lines(image, rle_line, total_pix_size, &g_tail); total_pix_size += rle_line->length; rle_line = rle_line->next; } image->height = total_pix_size / image->width; } static void find_all_possible_change_points(const Image *image, int line, int *x1_val, int *x1_size) { int i; H_Line *h_line = image->h_lines[line]; while(h_line) { if (h_line->length <= 1) { x1_val[(*x1_size)++] = h_line->x; } else if (h_line->length <= 2) { x1_val[(*x1_size)++] = h_line->x; x1_val[(*x1_size)++] = h_line->x + 1; } else if (h_line->length <= 3) { x1_val[(*x1_size)++] = h_line->x; x1_val[(*x1_size)++] = h_line->x + 1; x1_val[(*x1_size)++] = h_line->x + 2; } else { x1_val[(*x1_size)++] = h_line->x; x1_val[(*x1_size)++] = h_line->x + 1; x1_val[(*x1_size)++] = h_line->x + h_line->length - 2; x1_val[(*x1_size)++] = h_line->x + h_line->length - 1; } h_line = h_line->next; } } inline int get_pix_color(const Image *image, int x, int y, int line) { int pic_line = 0; H_Line *h_line = NULL; if (y == image->h_lines[line]->y) { pic_line = line; } else if (line>0 && y == image->h_lines[line-1]->y) { pic_line = line - 1; } else if (line < image->h_line_size-1 && y == image->h_lines[line+1]->y) { pic_line = line + 1; } else { return -1; } h_line = image->h_lines[pic_line]; while (h_line) { if (x >= h_line->x && x < h_line->x + h_line->length) { return h_line->color; } h_line = h_line->next; } return -1; } static int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } void find_image_egde_points(const Image *image, Point **points) { int *x1_val = NULL; int *x2_val = NULL; int i,j,k, pix_col, max_df, ret, x1_size,x2_size; int dx[8] = {-1,-1,-1, 1, 1, 1, 0, 0}; int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1}; Point *point = NULL, *tail = NULL; x1_val = (int *)malloc(8 * MAX_RLE_PAIRS * sizeof(int)); x2_val = (int *)malloc(8 * MAX_RLE_PAIRS * sizeof(int)); for (i=0; i<image->h_line_size; i++) { x1_size = 0; x2_size = 0; if (i>0 && image->h_lines[i-1]->y + 1 == image->h_lines[i]->y) { find_all_possible_change_points(image, i-1, x1_val, &x1_size); } find_all_possible_change_points(image, i, x1_val, &x1_size); if (i < image->h_line_size-1 && image->h_lines[i]->y + 1 == image->h_lines[i+1]->y) { find_all_possible_change_points(image, i+1, x1_val, &x1_size); } qsort(x1_val, x1_size, sizeof(int), cmp); if (x1_size > 0) { x2_val[x2_size++] = x1_val[0]; for (j=1; j<x1_size; j++) { if (x1_val[j] != x1_val[j-1]) { x2_val[x2_size++] = x1_val[j]; } } #ifdef DEBUG printf("x2 (size=%d):", x2_size); for (j=0; j<x2_size; j++) { printf("%d ", x2_val[j]); } printf("\n"); #endif for (j=0; j<x2_size; j++) { max_df = 0; pix_col = get_pix_color(image, x2_val[j], image->h_lines[i]->y, i); for (k=0; k<8; k++) { ret = get_pix_color(image, x2_val[j]+dx[k], image->h_lines[i]->y+dy[k], i); if (ret >= 0) { max_df = max(abs(pix_col-ret), max_df); } } point = (Point *)malloc(sizeof(Point)); point->next = NULL; point->color = max_df; point->x = x2_val[j]; point->y = image->h_lines[i]->y; if (tail == NULL) { *points = point; //header tail = point; } else { tail->next = point; tail = point; } } } } #ifdef DEBUG print_points(*points); #endif free(x1_val); free(x2_val); } inline int get_distance_between_two_point(const Point *p1, const Point *p2, int width) { int d, d1, d2; if (p1 == NULL || (p2->x == 1 && p2->y == 1)) { return 1; } d1 = (p1->y - 1) * width + p1->x; d2 = (p2->y - 1) * width + p2->x; d = d2 - d1; #ifdef DEBUG printf(" distance **** (%d, %d) - (%d, %d): d = %d, d1 = %d, d2 = %d\n", p1?p1->x:-1, p1?p1->y:-1, p2->x, p2->y, d, d1, d2); #endif return d; } void build_edge_RLE_image(Point *points, RLE_Image *rle_image, int width) { RLE_Line *rle_line = NULL; RLE_Line *tail = NULL; Point *point = NULL, *prev_point=NULL; int color, length; rle_image->width = 0; rle_image->rle_lines = NULL; rle_image->rle_line_size = 0; point = points; while (point) { if (rle_line == NULL) { rle_line = (RLE_Line *)malloc(sizeof(RLE_Line)); rle_line->next = NULL; rle_line->color = point->color; rle_line->length = get_distance_between_two_point(NULL, point, width); #ifdef DEBUG printf(" new ===> color = %d, len = %d\n", rle_line->color, rle_line->length); #endif if (tail == NULL) { tail = rle_line; } else { tail->next = rle_line; tail = rle_line; } if (rle_image->rle_lines == NULL) { rle_image->rle_lines = rle_line; rle_image->width = width; } rle_image->rle_line_size++; } else if (rle_line->color == point->color) { rle_line->length += get_distance_between_two_point(prev_point, point, width); #ifdef DEBUG printf(" update ===> color = %d, len = %d\n", rle_line->color, rle_line->length); #endif } else { #ifdef DEBUG printf(" end ===> color = %d, len = %d\n", rle_line->color, rle_line->length); #endif rle_line = NULL; continue; } prev_point = point; point = point->next; } } void solve_problem() { int i; RLE_Image rle_image; RLE_Image edge_rle_image; Image h_image; Point *edge_points = NULL; while (1) { //initialize memory memset(&rle_image, 0, sizeof(rle_image)); memset(&edge_rle_image, 0, sizeof(edge_rle_image)); memset(&h_image, 0, sizeof(h_image)); if (build_rle_image(&rle_image) == -1) { printf("0\n"); break; } #ifdef DEBUG print_RLE_image(&rle_image); #endif build_image(&rle_image, &h_image); #ifdef DEBUG print_image(&h_image); #endif find_image_egde_points(&h_image, &edge_points); build_edge_RLE_image(edge_points, &edge_rle_image, rle_image.width); print_RLE_image(&edge_rle_image); //free LIST memory FREE_LIST(rle_image.rle_lines, RLE_Line); FREE_LIST(edge_rle_image.rle_lines, RLE_Line); FREE_LIST(edge_points, Point); for (i=0; i<h_image.h_line_size; i++) { FREE_LIST(h_image.h_lines[i], H_Line); } if (h_image.h_lines) { free(h_image.h_lines); } } } int main() { solve_problem(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator