> ////////////////////////////////////////////////////////////////
> //		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