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

#define BYTE unsigned char

class CDetectEdge
{
public:
	CDetectEdge(int width)
	{
		m_width = width;
		m_buffer_size = width*3;
		m_buffer = new BYTE[m_buffer_size];
		m_out_buffer = new BYTE[width];

		m_current_index = 0;
		m_compute_row = 0;
		m_last_pixel = 0;
		m_last_pixel_length = 0;
	}

	~CDetectEdge()
	{
		delete[] m_buffer;
		delete[] m_out_buffer;
	}

	void WritePixelPair(BYTE pixel, int length)
	{
		int size;

		//End
		if(length <= 0)
		{
			size = m_current_index/m_width;
			if(m_current_index % m_width != 0)
				size++;
			while(size > m_compute_row)
			{
				ComputeLine();
				m_compute_row++;
			}
			printf("%d %d\n", m_last_pixel, m_last_pixel_length);
			printf("0 0\n");
			return;
		}
		//Optimize
		if(length > m_width*6)
		{
			size = (m_width - (m_current_index % m_width)) + m_width*2;
			WritePixelPair(pixel, size);
			size = length - size;
			if(m_last_pixel != 0)
			{
				printf("%d %d\n", m_last_pixel, m_last_pixel_length);
				m_last_pixel = 0;
				m_last_pixel_length = 0;
			}
			m_last_pixel_length += (int)(size / m_width - 1) * m_width;
			WritePixelPair(pixel, size % m_width + m_width);
			return;
		}
		//Normal
		while(length > 0)
		{
			size = (m_buffer_size - m_current_index);
			size = size < length ? size : length;
			memset(&m_buffer[m_current_index], pixel, size);
			m_current_index += size;
			length -= size;
			if(m_current_index >= m_buffer_size)
			{
				if(m_compute_row < 1)
				{
					ComputeLine();
					m_compute_row++;
				}
				ComputeLine();
				memcpy(m_buffer, &m_buffer[m_width], 2*m_width);
				m_current_index = 2*m_width;
			}
		}
	}

private:
	void ComputeLine()
	{
		int width = m_width;

		if(m_current_index < (m_compute_row+1)*m_width)
			width = m_current_index % m_width;
		DetectEdge(m_buffer, width, m_current_index/m_width, m_compute_row, m_out_buffer);
		m_last_pixel_length = PrintImage(m_out_buffer, width, m_last_pixel, m_last_pixel_length);
	}

	int PrintImage(BYTE *buffer, int size, BYTE &last_pixel, int length)
	{
		BYTE pixel = last_pixel;
		int len = length;
		for(int i=0; i<size; i++)
		{
			if(buffer[i] != pixel)
			{
				if(len > 0)
					printf("%d %d\n", pixel, len);
				pixel = buffer[i];
				len = 1;
			}
			else
				len++;
		}

		last_pixel = pixel;
		return len;
	}

	inline int DetectMax(BYTE value, BYTE &max)
	{
		if((value) > (max))
			(max) = (value);
		return max;
	}

	void DetectEdge(BYTE *buffer, int width, int height, int compute_row, BYTE *out_buffer)
	{
		bool hasUpper = compute_row > 0;
		bool hasNether = compute_row < height-1;
		BYTE *upper_row = &buffer[(compute_row-1)*width];
		BYTE *current_row = &buffer[compute_row*width];
		BYTE *nether_row = &buffer[(compute_row+1)*width];
		BYTE max_value;
		BYTE value;

		for(int i=0; i<width; i++)
		{
			max_value = 0;
			value = current_row[i];
			if(hasUpper)
			{
				if(i > 0)
					DetectMax(abs(upper_row[i-1] - value), max_value);
				if(i < width-1)
					DetectMax(abs(upper_row[i+1] - value), max_value);
				DetectMax(abs(upper_row[i] - value), max_value);
			}
			if(hasNether)
			{
				if(i > 0)
					DetectMax(abs(nether_row[i-1] - value), max_value);
				if(i < width-1)
					DetectMax(abs(nether_row[i+1] - value), max_value);
				DetectMax(abs(nether_row[i] - value), max_value);
			}

			if(i > 0)
				DetectMax(abs(current_row[i-1] - value), max_value);
			if(i < width-1)
				DetectMax(abs(current_row[i+1] - value), max_value);

			out_buffer[i] = max_value;
		}
	}

private:
	int m_width;
	BYTE *m_buffer;
	BYTE *m_out_buffer;
	int m_buffer_size;
	int m_current_index;
	int m_compute_row;
	BYTE m_last_pixel;
	int m_last_pixel_length;
};

int main()
{
	int width;
	int pixel;
	int length;
	CDetectEdge *lpDetectEdge = NULL;

	while(true)
	{
		scanf("%d", &width);
		if( width <= 0 )
			break;

		printf("%d\n", width);
		if(lpDetectEdge != NULL)
			delete lpDetectEdge;
		lpDetectEdge = new CDetectEdge(width);

		while(true)
		{
			scanf("%d%d", &pixel, &length);
			lpDetectEdge->WritePixelPair(pixel, length);
			if(length <= 0 && 0 == pixel)
				break;
		}
	}
	if(lpDetectEdge != NULL)
		delete lpDetectEdge;

	printf("0\n");
	return 0;
}

• Re:所有能找到的测试数据都通过了，就是过不了，贴代码请教 (46) Tullius 2011-05-06 17:06:02