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且不为0while ((cin>> iWid) && iWid){// 读入一组数据且不同时为0while ((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;// 准备下一张MAPvMap.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了。
?
如果考虑不周的话，还请网友提醒。
?