Colorado Potato Beetle(CF的某道) & 鬼畜宽搜

题意:

　　一个人在一张大图上走,给你路径与起点,求他走出的矩形面积并.(大概这个意思自行百度标题...

SOL:

　　与其说这是一道图论题不如说是一道生动活泼的STL-vector教学....

　　离散化宽搜,没什么别的...vector用得淋漓尽致...

Code:

　　

/*==========================================================================

# Last modified: 2016-03-18 08:32

# Filename: t1.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <deque>

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1]

#define pb push_back

#define find(a,b) lower_bound((a).begin(), (a).end(), (b))-(a).begin()

#define INF 10000000000

#define maxn 3000

#define maxm 100000

#define pi 3.1415926535898

#define _e 2.718281828459

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

ll n, x[maxn], x1 = INF/2, y1 = INF/2, ans = 0;

char d[maxn];

vector<ll> x2,y2;

int a[maxn][maxn];

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

void check(){

    FORP(i,0,x2.size()-1) printf("%lld ",x2[i]);

    printf("\n");

    FORP(i,0,y2.size()-1) printf("%lld ",y2[i]);

    cout << endl;

}

void mark(int ld,int rd,int lu,int ru) {

    if (ld>lu) swap(ld,lu); if (rd>ru) swap(rd,ru);

    for (int i=ld;i<=lu;i++)

        for (int j=rd;j<=ru;j++) a[i][j] = 1;

}

queue<int> qx,qy;

void bfs() {

    qx.push(0); qy.push(0);

    while (!qx.empty()){

        int nx=qx.front(),ny=qy.front();

        qx.pop(); qy.pop();

        FORP(i,0,3) {

            int xx=nx+dx[i],yy=ny+dy[i];

            if (xx<0||xx>=x2.size()||yy<0||yy>=y2.size()||a[xx][yy])

            continue;

            else {

                a[xx][yy]=2;

                qx.push(xx); qy.push(yy);

            }

        }

    }

    //FORP(i,0,3) dfs(xx+dx[i],yy+dy[i]);

}

void init(){

    read(n);

    x2.pb(0); x2.pb(INF);

    y2.pb(0); y2.pb(INF);

    FORP(i,0,n-1){

        x2.pb(x1); x2.pb(x1+1);

        y2.pb(y1); y2.pb(y1+1);

        cin >> d[i]; read(x[i]);

        if (d[i]=='R')x1+=x[i];if (d[i]=='L')x1-=x[i];

        if (d[i]=='U')y1+=x[i];if (d[i]=='D')y1-=x[i];

    }

    x2.pb(x1); x2.pb(x1+1);

    y2.pb(y1); y2.pb(y1+1);

   // check();

    sort(x2.begin(), x2.end()); sort(y2.begin(), y2.end());

    x2.erase(unique(x2.begin(),x2.end()),x2.end());

    y2.erase(unique(y2.begin(),y2.end()),y2.end());

   // check();

}

int main(){

    //freopen("a.in","r",stdin);

    init();

    int xnow=find(x2,INF/2),ynow=find(y2,INF/2);

    ll xx=INF/2, yy=INF/2;

    FORP(i,0,n-1){

        int x4=xnow,y4=ynow;

        if (d[i]=='R') xx+=x[i];if (d[i]=='L') xx-=x[i];

        if (d[i]=='U') yy+=x[i];if (d[i]=='D') yy-=x[i];

        xnow=find(x2,xx); ynow=find(y2,yy);

        mark(xnow, ynow, x4, y4);

    }

    bfs();

    FORP(i,0,x2.size()-1)

        FORP(j,0,y2.size()-1)

            if (a[i][j]!=2) ans+=(x2[i+1]-x2[i])*(y2[j+1]-y2[j]);

    printf("%lld\n",ans);

    return 0;

}