Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于AC了! 共享出来,希望大家一起指正!

Posted by qiangpengliu at 2016-09-19 22:19:17 on Problem 1009
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator