POJ 1009 解题报告 Edge Detection

1009是痛苦的一题啊。游程编码问题。

先说思路：只处理变化的点。产生变化的点会影响周围的8个点的编码。没有产生变化的点的编码值与前一天相同。当然，有几个特殊情况需要注意。

先上代码：

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef class Point
{
public:
	int iFirst;
	int iSecond;

	Point(int iF, int iS): iFirst(iF), iSecond(iS){};
}Pix, Pair;

vector<Pair> vMap;
vector<Pix> vResultMap;

int iWid;
int iPairV;
int iPairC;
int iTotal = 0;

void calculateMap();
int getCode(int iPos, int iRow, int iCol);
int getValue(int iPos);
int cmp(const void *pL, const void *pR);

int main ()
{
	// 读入map且不为0
	while ((cin>> iWid) && iWid)
	{
		// 读入一组数据且不同时为0
		while ((cin>> iPairV >> iPairC) && (iPairV || iPairC))
		{
			iTotal += iPairC;
			Pair tmpPair(iPairV, iPairC);
			vMap.push_back(tmpPair);
		}

		cout <<iWid<<endl;

		calculateMap();

		qsort(&vResultMap[0], vResultMap.size(), sizeof(Pix), cmp);

		int iCur = 0;
		int iSize = vResultMap.size();
		for(int i=0;i<iSize;i++)
		{
			if(vResultMap[iCur].iSecond == vResultMap[i].iSecond)
			{
				continue;
			}

			cout << vResultMap[iCur].iSecond << " " << vResultMap[i].iFirst - vResultMap[iCur].iFirst << endl;
			iCur = i;
		}
		cout << vResultMap[iCur].iSecond << " " << iTotal - vResultMap[iCur].iFirst << endl;
		cout<<"0 0"<<endl;

		// 准备下一张MAP
		vMap.clear();
		vResultMap.clear();
		iTotal = 0;
	}

	cout <<"0"<< endl;

	return 0;
}

void calculateMap()
{
	int iPairPos = 1;

	for (int iMap = 0; iMap <= vMap.size(); iMap ++)
	{
		int iRow = (iPairPos - 1)/iWid;
		int iCol = (iPairPos - 1)%iWid;

		// 此处处理1号点问题
		if (iCol == iWid - 1)
		{
			if ((iRow + 2)*iWid < iTotal)
			{
				Pix tmpPix(iPairPos + iWid, getCode(iPairPos + iWid + 1, iRow + 2, 0));
				vResultMap.push_back(tmpPix);
			}
		}

		for (int i = iRow - 1; i <= iRow + 1; i ++)
		{
			for (int j = iCol - 1; j <= iCol + 1; j ++)
			{
				int iPos = iWid*i+j+1;

				if (i <0 || j <0 || iPos > iTotal || j >= iWid )
				{
					continue;
				}

				Pix tmpPix(iWid*i+j, getCode(iPos, i, j));
				vResultMap.push_back(tmpPix);
			}
		}

		iPairPos += vMap[iMap].iSecond;
	}
}

int getCode(int iPos, int iRow, int iCol)
{
	int iMid = getValue(iPos);
	int r = 0;

	for (int i = iRow -1; i <= iRow + 1; i++)
	{
		for (int j = iCol - 1; j <= iCol + 1; j++)
		{
			int iTmpPos = iWid*i+j+1;
			if (iTmpPos == iPos || i < 0 || j < 0 || j >= iWid || iTmpPos > iTotal)
			{
				continue;
			}

			int iTmp = getValue(iTmpPos);
			if (abs(iMid - iTmp) > r)
			{
				r = abs(iTmp - iMid);
			}
		}
	}
	return r;
}

int getValue(int iPos)
{
	int iN = 0;

	int i;
	for (i = 0; iN < iPos; i ++)
	{
		iN += vMap[i].iSecond;
	}

	return vMap[i - 1].iFirst;
}

int cmp(const void *pL, const void *pR)
{
	Pix *pPixL = (Pix *)pL;
	Pix *pPixR = (Pix *)pR;

	return pPixL->iFirst - pPixR->iFirst;
}

 网上的代码使用这个思路的都有一个问题，在处理输入：

 

10
1 52
2 48
5 10
3 69
8 10
4 71
0 0
时，会出错。
如图：

 另一个需要注意的地方，是以上情况的特殊情况。

如图：

 

 辛苦了一下，终于把这题给KO了。

 

如果考虑不周的话，还请网友提醒。