kao shi di er ti(还没有订正)

// 离散化点 思路应该是对的 吧 但没时间去检查编译上的错误 
#include <bits/stdc++.h> 
using namespace std;
const int M =1005;
#define ri register int 
int n,sum;
struct dian{
    int x,y,id,bj,zlin;
}a[M],yuan[M],arr[M][M];
int m,X[M],Y[M],m2,vis[M][M];
void dfs(int a,int b,int zl,int xx,int yy)  // 1 up 2 xia ,3 zuo ,4 rou
{   
   if(arr[a][b].zlin)
   { 
     zl=arr[a][b].zlin;
     sum+=abs(arr[a][b].x-xx+1);
     sum+=abs(arr[a][b].y-yy+1);
     if(arr[a][b].id==1) return;
     xx=arr[a][b].x,yy=arr[a][b].y;
       if(zl==1) dfs(a,b+1,1,xx,yy);
       if(zl==2) dfs(a,b-1,2,xx,yy);
       if(zl==3) dfs(a-1,b,3,xx,yy);
       if(zl==4) dfs(a+1,b,4,xx,yy);
       return ;
   }if(arr[a][b].id==1)
   {
        sum+=abs(arr[a][b].x-xx+1);
     sum+=abs(arr[a][b].y-yy+1);
     return ;
   }
    arr[a][b].bj=1;
    if(zl==1) dfs(a,b+1,1,xx,yy);
       if(zl==2) dfs(a,b-1,2,xx,yy);
       if(zl==3) dfs(a-1,b,3,xx,yy);
       if(zl==4) dfs(a+1,b,4,xx,yy);
}
void dfs1(int a,int b)
{
    if(arr[a][b].id==2) return; // 
    if(a>m||a<1) return ;
    if(b>m2||b<1) return ;
     arr[a][b].bj=1; 
    dfs1(a+1,b);dfs1(a,b+1);
    dfs1(a-1,b);dfs1(a,b-1);
}
int main(){
    scanf("%d",&n);
    yuan[1].x=yuan[1].y=a[1].x=a[1].y=X[1]=Y[1]=1;
    a[1].id=1;yuan[1].id=1;
    for(ri i=2;i<=n+1;i++)
    {   char c[3];int b;
        scanf("%s%d",c,&b);
        if(c[0]=='R') a[i].x=a[i-1].x+b,a[i].y=a[i-1].y,a[i].zlin=3;
        if(c[0]=='L') a[i].x=a[i-1].x-b,a[i].y=a[i-1].y,a[i].zlin=4;
        if(c[0]=='U') a[i].y=a[i-1].y+b,a[i].x=a[i-1].x,a[i].zlin=2;
        if(c[0]=='D') a[i].y=a[i-1].y-b,a[i].x=a[i-1].x,a[i].zlin=1;
        X[i]=a[i].x;yuan[i].x=a[i].x; yuan[i].id=i;
        Y[i]=a[i].y; a[i].id=i;yuan[i].y=a[i].y;
    }
    sort(X+1,X+n+1+1);
    m=unique(X+1,X+n+1+1)-X-1;
    for(ri i=1;i<=n+1;i++)
    {
        a[i].x=lower_bound(X+1,X+m+1,a[i].x)-X;
    }
    sort(Y+1,Y+n+2);
     m2=unique(Y+1,Y+n+1+1)-Y-1;
    for(ri i=1;i<=n+1;i++)
    {
      a[i].y=lower_bound(Y+1,Y+m2+1,a[i].y)-Y;
    }
    for(ri i=1;i<=n+1;i++)
    {
        arr[a[i].x][a[i].y].id=i;
        arr[a[i].x][a[i].y].x=yuan[i].x;X[a[i].x]=yuan[i].x;
        arr[a[i].x][a[i].y].y=yuan[i].y;Y[a[i].y]=yuan[i].y;
        arr[a[i].x][a[i].y].bj=2;
    }
    dfs(a[n+1].x,a[n+1].y,a[n+1].zlin,a[n+1].x,a[n+1].y);
    dfs1(m,m2);
    for(ri i=1;i<=m;i++)
    for(ri j=1;j<=m2;j++)
    {
        if(arr[i][j].bj==0)
        {
            sum+=abs(X[j]-X[j-1]);
            sum+=abs(X[i]-X[i-1]);
        }
    }
    printf("%d
",sum);
    return 0; 
}
原文地址:https://www.cnblogs.com/Lamboofhome/p/11737524.html