北大ACM(POJ1009-Edge Detection)

 1 Memory: 648K        Time: 547MS
 2 Language: C++        Result: Accepted
 3 
 4 #include <iostream>
 5 #include <cstdlib>
 6 #include <map>
 7 #include <vector>
 8 using namespace std;
 9 
10 map<int,int> mp;
11 map<int,int> omp;
12 map<int, int>::iterator mp_Iter;
13 map<int, int>::iterator omp_Iter;
14 vector<int> st;
15 static int around[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
16 int getValue(int index)
17 {
18     int value=0;
19     for(mp_Iter = mp.begin(); mp_Iter != mp.end(); mp_Iter++)
20     {
21         if(index<mp_Iter->first) break;
22         value=mp_Iter->second;
23     }
24     return value;
25 }
26 int getMax(int index,int width,int count)
27 {
28     int center=getValue(index);
29     int h=index/width;
30     int max=0;
31     for(int i=0;i<8;i++)
32     {
33         int sub=index+around[i][0]*width+around[i][1];
34         if(h+around[i][0]==sub/width && sub>=0 && sub<count)
35         {
36             int a=getValue(sub);
37             max=abs(center-a)>max?abs(center-a):max;
38         }
39     }
40     return max;
41 }
42 void process(int width,int count)
43 {
44     for(int i=0; i < st.size(); i++)
45     {
46         int index=st.at(i);
47         omp.insert(pair<int,int>(index,getMax(index,width,count)));
48     }
49 }
50 int main()
51 {
52     int width;
53     while(cin>>width && cout<<width<<endl && width)
54     {
55         mp.clear();
56         omp.clear();
57         st.clear();
58         int v,l,count=0;
59         while(cin>>v>>l && l){//v有可能为0
60             mp.insert(pair<int,int>(count,v));
61             count+=l;
62         }
63         for(mp_Iter = mp.begin(); mp_Iter != mp.end(); mp_Iter++)
64         {
65             for(int i=-1;i<2;i++)
66             {
67                 for(int j=-1;j<2;j++)
68                 {
69                     int index=mp_Iter->first+i*width+j;
70                     if(index>=0 && index <count)
71                         st.push_back(index);
72                 }
73             }
74         }
75         st.push_back(width);
76         st.push_back(count-width);
77         process(width,count);
78         
79         omp_Iter = omp.begin();
80         int st=omp_Iter->first;
81         int val=omp_Iter->second;
82         omp_Iter++;
83         for(;omp_Iter != omp.end(); omp_Iter++)
84         {
85             if(omp_Iter->second != val)
86             {
87                 cout<<val<<" "<<omp_Iter->first-st<<endl;
88                 st=omp_Iter->first;
89                 val=omp_Iter->second;
90             }
91         }
92         cout<<val<<" "<<count-st<<endl;
93         cout<<"0 0"<<endl;
94     }
95     return 0;
96 }