PKU 1009

Edge Detection
AとBの境目が画像の端にある場合も含めて、入力画像の値がA→Bと変化するときに出力画像の値が変わる可能性があるのは、下図の赤太線の部分のみ。

1. 出力画像の値が変わる可能性がある場所で、RLEのブロックを分割。
2. 分割したブロックそれぞれで出力画像の値を求める。
3. 同じ値のブロックを連結する。

RLEブロック数をnとしてO(n^2)なら充分かと思ったが、Time Limit Exceed。get関数を一工夫して指定したブロックから探し始めるようにすると間に合った。

最後の0を出力するのを忘れていて悩んだ。

#include <iostream>
#include <algorithm>
#include <list>

using namespace std;

struct BLOCK
{
    int val, len, pos;
    BLOCK( int v, int l, int p ) : val(v), len(l), pos(p) {}
};

void split( list<BLOCK> *image, int pos );
int get( list<BLOCK> *image, int pos, list<BLOCK>::iterator p );

int main()
{
    while ( true )
    {
        int w, h;
        list<BLOCK> image, temp;
        list<BLOCK>::iterator b, tb;

        //  read input image
        cin >> w;
        if ( w == 0 )
            break;

        int p = 0;
        while ( true )
        {
            int v, l;
            cin >> v >> l;
            if ( l == 0 )
                break;

            image.push_back( BLOCK(v,l,p) );

            p += l;
        }

        h = p / w;

        //  split RLE block at the position
        //  where the value of output image may change
        temp = image;

        for ( b=temp.begin(); b!=temp.end(); b++ )
        {
            for ( int y=-w; y<=w; y+=w )
            for ( int x=-1; x<=1; x+=1 )
                split( &image, b->pos+y+x );
        }
        split( &image, w*(h-1) );

        //  calc the differences
        temp = image;

        for ( b=image.begin(), tb=temp.begin();
              b!=image.end(); b++, tb++ )
        {
            int ys = b->pos/w > 0   ? -w : 0;
            int ye = b->pos/w < h-1 ?  w : 0;
            int xs = b->pos%w > 0   ? -1 : 0;
            int xe = b->pos%w < w-1 ?  1 : 0;

            int m = 0;
            for ( int y=ys; y<=ye; y+=w )
            for ( int x=xs; x<=xe; x+=1 )
            {
                int c = b->val;
                int n = get( &temp, b->pos+y+x, tb );

                m = max( m, abs(c-n) );
            }

            b->val = m;
        }

        //  merge same-colored blocks
        for ( b=image.begin(); b!=image.end(); )
        {
            tb = b,  tb++;

            for ( tb=b, tb++;
                  tb != image.end()  &&  b->val == tb->val; )
                b->len += tb->len,
                tb = image.erase(tb);

            b = tb;
        }

        //  output image
        cout << w << endl;

        for ( b=image.begin(); b!=image.end(); b++ )
            cout << b->val << " " << b->len << endl;

        cout << "0 0" << endl;
    }

    cout << 0 << endl;

    return 0;
}

//  split RLE block at specified position
void split( list<BLOCK> *image, int pos )
{
    if ( pos <= 0 )
        return;

    list<BLOCK>::iterator b;

    for ( b=image->begin(); b!=image->end(); b++ )
        if ( b->pos + b->len >= pos )
            break;

    if ( b == image->end() )
        return;
    
    if ( pos < b->pos + b->len )
    {
        image->insert( b, BLOCK(b->val,pos-b->pos,b->pos) );
        b->len -= pos - b->pos;
        b->pos = pos;
    }
}

//  get the value of specified position
int get( list<BLOCK> *image, int pos, list<BLOCK>::iterator p )
{
    if ( p->pos <= pos  &&  pos < p->pos + p->len )
        return p->val;

    list<BLOCK>::iterator b = p;
    list<BLOCK>::iterator f = p;

    while ( true )
    {
        if ( b != image->begin() )
        {
            b--;
            if ( b->pos <= pos  &&  pos < b->pos + b->len )
                return b->val;
        }

        f++;
        if ( f != image->end() )
        {
            if ( f->pos <= pos  &&  pos < f->pos + f->len )
                return f->val;
        }
        else
            f--;
    }
}