暴力——cf1202C

谁借莪１个温暖的怀抱￠ 2023-10-11 09:09 16阅读 0赞

直接去考虑细节很多，不如暴力做

即在四个方向到达最远前向反方向走一步，答案肯定是从这四种情况+不多走里出的

#include<bits/stdc++.h>
    using namespace std;
    #define N 200005
    char s[N],t[N];
    int n,w,h,u,d,l,r,x,y,pu,pd,pl,pr;
    
    void insert(int pos,char ch){
        //在pos前塞入ch 
        int len=strlen(t+1);
        for(int i=len;i>=pos;i--)
            t[i+1]=t[i];
        t[pos]=ch; 
    }
    void calc(){
        int len=strlen(t+1),u=0,d=0,l=0,r=0,x=0,y=0;
        for(int i=1;i<=len;i++){
            if(t[i]=='W')y++;
            if(t[i]=='S')y--;
            if(t[i]=='A')x--;
            if(t[i]=='D')x++;
            if(y>u)u=y;
            if(y<d)d=y;
            if(x>r)r=x;
            if(x<l)l=x;
        }
        w=r-l+1;h=u-d+1;
    }
    
    
    int main(){
        int T;cin>>T;
        while(T--){
            u=0,d=0,l=0,r=0,x=0,y=0;
            pu=pd=pl=pr=0;
            memset(s,0,sizeof s);
            scanf("%s",s+1);
            n=strlen(s+1);
            for(int i=1;i<=n;i++){
                if(s[i]=='W')y++;
                if(s[i]=='S')y--;
                if(s[i]=='A')x--;
                if(s[i]=='D')x++;
                if(y>u)u=y,pu=i;
                if(y<d)d=y,pd=i;
                if(x>r)r=x,pr=i;
                if(x<l)l=x,pl=i;
            }
            w=r-l+1;h=u-d+1;
            long long ans=(long long)w*h;
            memset(t,0,sizeof t);
            memcpy(t,s,sizeof s);
            if(pu)insert(pu,'S');
            calc();
            ans=min(ans,1ll*w*h);
            
            memset(t,0,sizeof t);
            memcpy(t,s,sizeof s);
            if(pd)insert(pd,'W');
            calc();
            ans=min(ans,1ll*w*h);
            
            memset(t,0,sizeof t);
            memcpy(t,s,sizeof s);
            if(pr)insert(pr,'A');
            calc();
            ans=min(ans,1ll*w*h);
            
            memset(t,0,sizeof t);        
            memcpy(t,s,sizeof s);
            if(pl)insert(pl,'D');
            calc();
            ans=min(ans,1ll*w*h);
            
            cout<<ans<<'\n';
            
        }
    }
    /*
    4
    DSAWWAW
    D
    WA
    WSSW
    */

转载于:https://www.cnblogs.com/zsben991126/p/11515693.html