http://poj.org/problem?id=1009 (题目链接)
不得不说，poj上的水题还是质量非常高的= =，竟然让本大爷写了一下午。
转自：http://blog.sina.com.cn/s/blog_6e63f59e01012mxb.html
题意
给出一个矩阵，有一种简单的算法：将矩阵中的每一个点的值与他周围的八个点相减，然后将当前点更新为绝对值最大的。求转换后的矩阵，输入的矩阵是以 “压缩法”表示的，同时也要求转换后的矩阵也以“压缩法”的形式表示。
Solution
首先，暴力必挂，这是题目的善意提醒。
于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的蒟蒻。
再然后就思维混乱了。于是看网上各位大神的解题报告。很神奇的一个搞法。瞬间被震惊。发现了一个道理，有时候从这个角度搞不通的时候，换一个更直接的角度往往一下就搞通了。是的。
首先可以看出来，这个最终的答案中，肯定会有某些连续段，答案是不变的，这些连续段又和原图有关。我自己的思路就是，先找出在原图的某一连续段中，答案值可能改变的几个像素（做标记），再一次次跳跃到这几个像素中计算它们的答案值，但是问题就是，怎么样的像素才是需要计算的像素。
如图的一个map：
第一个x显然是需要标记的。然后，可以直接跳跃到第4个x，因为此时它的周围多了一个z，答案可能改变，而第二、三个x显然答案和第一个是一样的。再然后，y的第一个也肯定要标记，因为主体变了。然后到了坐标为(2,3)的y，它需要标记是因为它的周围多了一个m。于是以此类推完成。虽然这个搞法看似可以，但这么多的细节要考虑，况且格子数是10^9，以我的水平注定挂。该怎么办呢。在看了各位大神的题解之后，发现其实我只要把需要标记的格子标记出来，并且把每一连续段的分段画出来，就可以发现很神奇的东西：
紫色标注的都是要标记的格子，红色边框的代表这一个连续段的起始格。我们可以发现，每个连续段的起始格，都是要标记的格子，同时，每个要标记的格子，都是一个连续段起始格的周围8个格子中的一个。所以，改进的搞法就很清楚了：只需要一个个枚举每个连续段的起始格，并计算它和它四周8个格子的答案值，最后统计答案的时候按照位置先后排序，答案中相同的连续段就合并。因为最多只有1000个连续段，所以不管是时间还是空间都不会超。
代码
// poj1009
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<set>
#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<b.pos;
}
int getnum(int pos) {
int p=0,i=0;
while (p<pos) p+=a[++i][1];
return a[i][0];
}
int getcode(int pos) {
int num=getnum(pos),res=0;
int x=(pos-1)/n+1;
int 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 || 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);
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
",tmp.code,ans[i].pos-tmp.pos);
tmp=ans[i];
}
printf("%d %d
",tmp.code,tot-tmp.pos+1);
printf("0 0
");
}
printf("0
");
return 0;
}