(题目链接)

不得不说，poj上的水题还是质量非常高的= =，竟然让本大爷写了一下午。

转自：

题意

　　给出一个矩阵，有一种简单的算法：将矩阵中的每一个点的值与他周围的八个点相减，然后将当前点更新为绝对值最大的。求转换后的矩阵，输入的矩阵是以 “压缩法”表示的，同时也要求转换后的矩阵也以“压缩法”的形式表示。

Solution

　　首先，暴力必挂，这是题目的善意提醒。

　　于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的蒟蒻。

　　再然后就思维混乱了。于是看网上各位大神的解题报告。很神奇的一个搞法。瞬间被震惊。发现了一个道理，有时候从这个角度搞不通的时候，换一个更直接的角度往往一下就搞通了。是的。

　　首先可以看出来，这个最终的答案中，肯定会有某些连续段，答案是不变的，这些连续段又和原图有关。我自己的思路就是，先找出在原图的某一连续段中，答案值可能改变的几个像素（做标记），再一次次跳跃到这几个像素中计算它们的答案值，但是问题就是，怎么样的像素才是需要计算的像素。 

　　如图的一个map：

　　第一个x显然是需要标记的。然后，可以直接跳跃到第4个x，因为此时它的周围多了一个z，答案可能改变，而第二、三个x显然答案和第一个是一样的。再然后，y的第一个也肯定要标记，因为主体变了。然后到了坐标为(2,3)的y，它需要标记是因为它的周围多了一个m。于是以此类推完成。虽然这个搞法看似可以，但这么多的细节要考虑，况且格子数是10^9，以我的水平注定挂。该怎么办呢。在看了各位大神的题解之后，发现其实我只要把需要标记的格子标记出来，并且把每一连续段的分段画出来，就可以发现很神奇的东西：

　　紫色标注的都是要标记的格子，红色边框的代表这一个连续段的起始格。我们可以发现，每个连续段的起始格，都是要标记的格子，同时，每个要标记的格子，都是一个连续段起始格的周围8个格子中的一个。所以，改进的搞法就很清楚了：只需要一个个枚举每个连续段的起始格，并计算它和它四周8个格子的答案值，最后统计答案的时候按照位置先后排序，答案中相同的连续段就合并。因为最多只有1000个连续段，所以不管是时间还是空间都不会超。

代码

// poj1009#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f;}const int maxn=1010;struct data {int pos,code;}ans[maxn<<3];int a[maxn][2],n,cnt,tot;bool cmp(data a,data b) { return a.pos
            
             n || tpos>tot || tpos==pos) continue; int tmp=getnum(tpos); if (abs(tmp-num)>res) res=abs(tmp-num); } return res;}int main() { while (scanf("%d",&n)!=EOF && n) { int x,y; cnt=tot=0; while (scanf("%d%d",&x,&y)!=EOF && y>0) { a[++cnt][0]=x;a[cnt][1]=y; tot+=y; } printf("%d\n",n); int pos=1,k=0; for (int p=1;p<=cnt+1;p++) { x=(pos-1)/n+1; y=(pos-1)%n+1; for (int i=x-1;i<=x+1;i++) for (int j=y-1;j<=y+1;j++) { int tpos=(i-1)*n+j; if (i<1 || j<1 || j>n || tpos>tot) continue; ans[++k].pos=tpos; ans[k].code=getcode(tpos); } pos+=a[p][1]; } sort(ans+1,ans+1+k,cmp); data tmp=ans[1]; for (int i=1;i<=k;i++) { if (ans[i].code==tmp.code) continue; printf("%d %d\n",tmp.code,ans[i].pos-tmp.pos); tmp=ans[i]; } printf("%d %d\n",tmp.code,tot-tmp.pos+1); printf("0 0\n"); } printf("0\n"); return 0;}