Question:http://poj.org/problem?id=1009
問題點:RLE編碼。
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 }