`
ysshuai19
  • 浏览: 15318 次
  • 性别: Icon_minigender_1
  • 来自: 西安
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

POJ 1009 解题报告 Edge Detection

    博客分类:
  • POJ
阅读更多

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了。

 

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

 

  • 大小: 50.7 KB
  • 大小: 25.9 KB
0
0
分享到:
评论

相关推荐

    POJ1009-Edge Detection

    【描述】"北大POJ1009-Edge Detection 解题报告+AC代码" 题目要求编写一个程序,根据输入的二维矩阵表示的图像,计算并输出其边缘。解题报告通常会包含问题分析、算法选择、代码实现以及测试案例等部分。AC代码代表...

    poj1009 Edge Detection 可以直接AC的

    poj1009 Edge Detection 可以直接AC的

    poj 3414解题报告

    poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告

    poj 1012解题报告

    poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告

    poj 2329解题报告

    poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告

    poj 1440解题报告

    poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告

    poj 3083解题报告

    poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告

    poj 1659解题报告

    poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告

    poj 3720解题报告

    poj 3720解题报告poj 3720解题报告poj 3720解题报告poj 3720解题报告

    北大poj解题报告

    这个“北大poj解题报告”包含了作者在使用POJ平台解题过程中的学习总结和经验分享,旨在帮助软件工程专业的学生提升编程能力和算法理解。 解题报告通常会涵盖以下几个方面: 1. **基础算法讲解**:解题报告中可能...

    poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告

    poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...

    poj1691解题报告

    ### poj1691解题报告 #### 题目信息 - **题目名称**:Painting A Board - **时间限制**:1S - **内存限制**:1000K - **提交总数**:62 - **通过总数**:35 - **来源**:...

    acm竞赛----北大poj详细解题报告

    【ACM竞赛与北大POJ解题报告】 在编程竞赛领域,ACM(国际大学生程序设计竞赛,简称ACM/ICPC)是一项极具影响力的比赛,它挑战参赛者的算法设计、问题理解和快速编码能力。北京大学(Peking University)的在线判题...

    80道POJ解题报告

    【标题】"80道POJ解题报告"所涉及的知识点主要集中在ACM(国际大学生程序设计竞赛)和POJ(编程Online Judge系统)上。POJ是北京大学主办的一个在线编程竞赛平台,广泛用于训练和提升程序员的算法设计与实现能力。80...

    北大ACM_POJ_解题报告

    【北大ACM_POJ_解题报告】是北京大学ACM在线评测系统POJ的解题资源集合,这个压缩包包含了对POJ平台上的各种类型ACM竞赛题目的详细解答。ACM,全称国际大学生程序设计竞赛(International Collegiate Programming ...

    POJ 1316解题报告

    【POJ 1316 解题报告】 本题源自北京大学举办的ACM竞赛,题号为POJ 1316,主要涉及算法设计和数组的应用。题目要求找到10000以内的所有self-number,并输出它们。Self-number是一个特殊的整数序列,它的定义是该数...

    poj 2392 解题报告

    《POJ 2392解题报告:高效计算最高堆积高度》 本文将深入解析POJ 2392这个编程题目,该题目要求利用给定的不同高度、耐压性和数量的block,来确定能够堆叠出的最大高度。解决这个问题的关键在于运用排序和动态规划...

    poj2828解题报告

    这篇解题报告主要介绍了如何解决POJ2828这个编程题目。该题目涉及的数据结构是区间树(Interval Tree),这是一种用于高效处理区间查询和修改的树形数据结构。在这个问题中,我们需要根据输入的元素位置和值,构建一...

    ACM Poj Pku 解题报告答案 打包 下载 600多题 史上最全

    ACM Poj Pku 解题报告答案 打包 下载 600多题 史上最全 不是网上乱传的200多题,更不是100多题就挂着10分才能下的题 下了这个 大家也不要浪费分数去下载其它版本的了,基本上都有 共享 一起进步 中国加油 ACMer...

    本人整理的POJ解题报告大全

    【POJ解题报告大全】是我精心整理的一份编程题解集合,主要涵盖了在Programming Online Judge(POJ)平台上遇到的250道经典题目。POJ是一个著名的在线编程竞赛平台,它为程序员提供了大量的算法练习题目,是提高编程...

Global site tag (gtag.js) - Google Analytics