POJ1009解题报告

港控/mmm° 2022-08-13 17:43 256阅读 0赞

保送之后都是项目的事情，一直没有时间写acm题，今天刚好礼拜六尝试着继续之前的工作，争取以后每周能够写上1-2个poj。很久没写算法题感觉自己的智商已经完全不够用了。

说说这题，题目的大概意思很简单，完成输出矩阵（按照题目规定的编码方式对输入矩阵的每一个元素进行一一映射）。编码方式就不说了，一看就懂。

当然以我的智商只能想出二维数组+暴力搜索这种方式，但是发现题目要求的像素个数>10^9， 开数组的话肯定不行。

自己尝试着一个方法，比如在一组（数值，个数）中，如果周围的8个（边缘和4个角的像素要小于这个数）像素包含的value有相同的属性，便认为他们性质相同，那么他们必然有相同的映射。我的方法是：每一组每一组的遍历，获取每一组每一个像素的性质，相同的存入output 结构体中（Value和Count），写完之后，测试第一组数据成功，第二组数据一看傻眼了，太大了根本过不了。 猛然想到我傻啊，每一组每一个像素的遍历，那不就是暴搜嘛，简直是自己打自己脸。

无奈看大神博客，才知道跳跃搜索编码这个十分精妙的算法，当然，要完全理解我建议得画个图（再另一个大神的博客中看到图）看一看。

参考博客：[http://blog.sina.com.cn/s/blog\_6e63f59e01012mxb.html][http_blog.sina.com.cn_s_blog_6e63f59e01012mxb.html]（带图）

[http://blog.csdn.net/lyy289065406/article/details/6648671][http_blog.csdn.net_lyy289065406_article_details_6648671]

下面说说我看了博客后自己写这道题时的问题：

1.边界。包括边界，四角（3x3方阵），如图示，红色部分为需(ke)要(neng)注(yue)意(jie)的地方(图画的丑不要介意)。

![Center][]

2.索引值。索引值从1开始计算，用代数式模拟的行号与列号是从0开始计算，反过来，用公式从行号列号到索引的时候也需要+1。

代码如下（原谅与大神代码很相似，因为单步的时候拿大神的代码对比。）：

/*
    Arthur:near
    Date:2014/11/08
    Note:Poj1009
    */
    #include <iostream>
    using namespace std;
    
    #define size 1000
    
    typedef class Map
    {
    	public:
    		int pos;			//位置
    		int code;			//编码
    }output;					//输出Map class
    
    typedef class Pair
    {
    	public:
    		int value;			//值
    		int count;			//连续个数
    }input;						//输入Pair
    int total;
    
    input inputPair[size];		//每个Pair的上线为1000
    int width;					//输入宽
    
    output outputMap[size*8];	//每个像素点都依赖于周围的8个点
    
    /*获取绝对值*/
    int getAbs(int a,int b)
    {
    	int result=a-b;
    	return result>=0?result:(-result);
    }
    
    /*获取输入的索引为pos的值*/
    int getInputValue(int pos)
    {
    	int i=0;
    	int p=0;
    	while(p<pos)
    	{
    		p+=inputPair[i++].count;
    	}
    	return inputPair[i-1].value;
    }
    
    /*比较*/
    int cmp(const void* a,const void* b)
    {
    	output* x=(output*)a;
    	output* y=(output*)b;
    	return x->pos - y->pos;
    }
    
    /*从输入的某个像素点的获取该索引处的编码（最大绝对值）*/
    int getCode(int pos)
    {
    	int curCode=getInputValue(pos);
    	int maxAbs=0;
    	int row = (pos-1)/width;
    	int col = (pos-1)%width;
    	for(int i=row-1; i<=row+1 ;i++)
    	{
    		for(int j=col-1; j<=col+1 ;j++)
    		{
    			int inpos=i*width+j;
    			if(i<0 || j<0 || j+1>width||inpos+1 > total || inpos==pos-1)	//排除边缘没有像素的点和本身的像素值
    				continue;
    			
    			int inCode=getInputValue(inpos+1);
    			if(maxAbs < getAbs(inCode,curCode))
    				maxAbs = getAbs(inCode,curCode);
    		}
    	}
    	return maxAbs;
    }
    
    int main()
    {
    	//cin>>width;
    	int k;
    	while(cin>>width && width>0)
    	{
    		int value;
    		int count;
    		k=0;
    		total=0;
    		while(cin>>value>>count && count !=0)
    		{
    			inputPair[k].value=value;
    			inputPair[k++].count=count;
    			total+=count;
    		}
    		cout<<width<<endl;
    		int num=k;
    		int pos=1;
    		int outpos=0;
    		for(int p=0;p<=num;p++)
    		{
    			int row=(pos-1)/width;
    			int col=(pos-1)%width;
    			for(int i=row-1;i<=row+1;i++)        
                    for(int j=col-1;j<=col+1;j++)  
                    {  
                        int inpos=i*width+j;  
      
                        if(i<0 || j<0 || j+1>width || inpos+1>total)  
                            continue;  
      
                        outputMap[outpos].pos=inpos+1;  
                        outputMap[outpos++].code=getCode(inpos+1);  
                    }  
                pos+=inputPair[p].count;  
            }
    		qsort(outputMap,outpos,sizeof(output),cmp);
    		/*输出*/
    		output temp=outputMap[0];
    		for(int i=0 ;i<outpos;i++)
    		{
    			//output temp=outputMap[0];
    			if(temp.code==outputMap[i].code)
    				continue;
    			cout<<temp.code<<" "<<outputMap[i].pos-temp.pos<<endl;
    		//	cout<<"0 0"<<endl;
    			temp=outputMap[i];
    		}
    		cout<<temp.code<<" "<<total-temp.pos+1<<endl;
    		cout<<"0 0"<<endl;
    	}
    	cout<<0<<endl;
    	return 0;
    }

[http_blog.sina.com.cn_s_blog_6e63f59e01012mxb.html]: http://blog.sina.com.cn/s/blog_6e63f59e01012mxb.html
[http_blog.csdn.net_lyy289065406_article_details_6648671]: http://blog.csdn.net/lyy289065406/article/details/6648671
[Center]: /images/20220810/dea4dcba688b4473b076dba4a172586c.png