////////////////////////////////////////////////////////////////
//		Poj 1009: Edge Detection	Author: Mayfly
//		Memory: 596K				Time: 79MS
//		Language: C++				Result: Accepted
////////////////////////////////////////////////////////////////
#include<iostream>
#include<map>

using namespace std;

#define MAX_SIZE 1001
// 带参宏效率远高于math库函数
#define ABS(x) ( (x) < 0 ? -(x) : (x) )
#define MAX(a,b) ( (a) > (b) ? (a) : (b) )

// 记录关键点及周围8方向格子结果
typedef map<unsigned int, unsigned char> Pixel;
Pixel pix;

// 输入记录
int RLE[MAX_SIZE][3];
int width/* 表格宽度 */, total/* 表格格子总数 */, count/* RLE pairs 长度 */;

// 从RLE中获取第i个格子的输入值（二分查找）
unsigned char GetValue( int i )
{
	int left = 0;
	int right = count-1;
	/*if( RLE[right][2] <= i )
		return RLE[right][0];*/

	int middle;

	while(left<right)
	{
		middle = ( left + right ) >> 1;

		if( i< RLE[middle][2] )
			right = middle - 1;
		else if( i > RLE[middle+1][2] )
			left = middle + 1;
		else if( i == RLE[middle+1][2] )
			return RLE[middle+1][0];
		else
			return RLE[middle][0];
	}

	return RLE[right][0];
}

// 填写第i个格子的输出值
void SetValue( int i )
{
	if( pix[i] > 0 ) return;

	unsigned char ret = 0;

	int col = i % width;

	if( i >= width )
	{
		// ↑
		ret = MAX( ABS( GetValue( i ) - GetValue( i-width ) ), ret );

		// ↖
		if( col > 0 )
			ret = MAX( ABS( GetValue( i ) - GetValue( i-width-1 ) ), ret );

		// ↗
		if( col < width-1 )
			ret = MAX( ABS( GetValue( i ) - GetValue( i-width+1 ) ), ret );
	}

	if( i < total-width )
	{
		// ↓
		ret = MAX( ABS( GetValue( i ) - GetValue( i+width ) ), ret );

		// ↙
		if( col > 0 )
			ret = MAX( ABS( GetValue( i ) - GetValue( i+width-1 ) ), ret );

		// ↘
		if( col < width-1 )
			ret = MAX( ABS( GetValue( i ) - GetValue( i+width+1 ) ), ret );
	}

	// ←
	if( col > 0 )
		ret = MAX( ABS( GetValue( i ) - GetValue( i-1 ) ), ret );

	// →
	if( col < width-1 )
		ret = MAX( ABS( GetValue( i ) - GetValue( i+1 ) ), ret );

	pix[i] = ret;
}

// 处理第i个格子及其周围8方向的格子（调用SetValue函数，含出界判断）
void DealAround( int i )
{
	// 中间（自己）
	SetValue( i );

	int col = i % width;
	//int row = i / width;

	if( i >= width )
	{
		// ↑
		SetValue( i-width );

		// ↖
		if( col > 0 )
			SetValue( i-width-1 );

		// ↗
		if( col < width-1 )
			SetValue( i-width+1 );
	}

	if( i < total-width )
	{
		// ↓
		SetValue( i+width );

		// ↙
		if( col > 0 )
			SetValue( i+width-1 );

		// ↘
		if( col < width-1 )
			SetValue( i+width+1 );
	}

	// ←
	if( col > 0 )
		SetValue( i-1 );

	// →
	if( col < width-1 )
		SetValue( i+1 );
}

// 通过RLE分析哪些为关键点（每个RLE的首节点、第一个换行、最后一个换行）
void Analysis()
{
	int i, col, row, enter;
	
	for( int l=0; l<count; )
	{
		i = RLE[l][2];
		col = i % width;
		row = i / width;

		// 每个RLE pairs的开头即为关键点之一
		DealAround(i);

		// 上一个RLE的最后一个跨行首格
		if( col > 1 ) // 当前RLE开始于第1、2列时，enter会被标记
		{
			enter = ( RLE[l][2] - 1 ) / width * width;
			DealAround( enter );
		}

		// 第一个跨行首格
		enter = ( row + 1 ) * width;
		if( enter < RLE[++l][2]-1 )	// 当enter紧临结尾时，会被下一个RLE开头标记
			DealAround( enter );
	}

	// 最后一个RLE的第一个跨行首格
	enter = ( RLE[count-1][2] + 1 ) * width;
	if( enter < total )
		DealAround( enter );

	/*// 处理换行的第一个节点，当width=3时，行数最多，为最坏情况（此方法会导致内存超限）
	if( width > 2 )
	{
		for( int i=width; i<total; i+=width )
			SetValue( i );
	}*/
}

// 根据map中记录的关键点等计算值，按格式要求输出结果
void Output()
{
	Pixel::iterator it = pix.begin();
	unsigned char value = it->second;
	int i = 0, start = 0;

	cout << width << endl;

	while(1)
	{
		while( value == it->second )
		{
			++it;
			++i;
		
			if( pix.end() == it )
			{
				cout << (int)value << ' ' << total-start << endl;
				cout << "0 0\n";
				pix.clear();
				return;
			}
		}

		cout << (int)value << ' ' << it->first-start << endl;
		start = it->first;
		value = it->second;
	}
}

int main()
{
	while(1)
	{
		cin>>width;

		if( 0 == width ) break;

		total = 0;

		for( int i=0; i<MAX_SIZE; ++i )
		{
			cin>>RLE[i][0]>>RLE[i][1];

			RLE[i][2] = total;

			total += RLE[i][1];

			if( 0==RLE[i][0] && 0==RLE[i][1] )
			{
				count = i;
				break;
			}
		}

		//start = clock();
		Analysis();
		Output();
		//cout<<"Time: "<<clock()-start<<endl;
	}

	cout<<"0\n";

	return 0;
}

附一个测试数据：
输入
3
1 2
2 3
6 3
7 4
0 0
0
输出
3
1 1
5 1
4 2
5 2
4 2
5 1
1 3
0 0
0

• Re:AC了，尽管时间和内存不是很理想。关键点要注意每个RLE的首换行首格和末行首格 (4990) 3187180646 2024-03-01 14:53:37
• Re:AC了，尽管时间和内存不是很理想。关键点要注意每个RLE的首换行首格和末行首格 (4990) 3187180646 2024-03-01 14:53:48