time limit per test : 2 seconds
memory limit per test : 256 megabytes
分數：2100
You have a string s s s— a sequence of commands for your toy robot. The robot is placed in some cell of a rectangular grid. He can perform four commands:
'W' — move one cell up;
'S' — move one cell down;
'A' — move one cell left;
'D' — move one cell right.
Let G r i d ( s ) Grid(s) Grid(s) be the grid of minimum possible area such that there is a position in the grid where you can place the robot in such a way that it will not fall from the grid while running the sequence of commands s. For example, if s = D S A W W A W s=DSAWWAW s=DSAWWAW then G r i d ( s ) Grid(s) Grid(s) is the 4 × 3 4×3 4×3 grid:
you can place the robot in the cell ( 3 , 2 ) (3,2) (3,2);
the robot performs the command ′ D ′ 'D' ′D′ and moves to ( 3 , 3 ) (3,3) (3,3);
the robot performs the command ′ S ′ 'S' ′S′ and moves to ( 4 , 3 ) (4,3) (4,3);
the robot performs the command ′ A ′ 'A' ′A′ and moves to ( 4 , 2 ) (4,2) (4,2);
the robot performs the command ′ W ′ 'W' ′W′ and moves to ( 3 , 2 ) (3,2) (3,2);
the robot performs the command ′ W ′ 'W' ′W′ and moves to ( 2 , 2 ) (2,2) (2,2);
the robot performs the command ′ A ′ 'A' ′A′ and moves to ( 2 , 1 ) (2,1) (2,1);
the robot performs the command ′ W ′ 'W' ′W′ and moves to ( 1 , 1 ) (1,1) (1,1);
.
You have 4 4 4 extra letters: one ′ W ′ 'W' ′W′, one ′ A ′ 'A' ′A′, one ′ S ′ 'S' ′S′, one ′ D ′ 'D' ′D′. You’d like to insert at most one of these letters in any position of sequence s to minimize the area of G r i d ( s ) Grid(s) Grid(s).What is the minimum area of G r i d ( s ) Grid(s) Grid(s) you can achieve?
Input
The first line contains one integer T ( 1 ≤ T ≤ 1000 ) T(1≤T≤1000) T(1≤T≤1000) — the number of queries.
Next T T T lines contain queries: one per line. This line contains single string s ( 1 ≤ ∣ s ∣ ≤ 2 ⋅ 1 0 5 , s i ∈ W , A , S , D ) s(1≤|s|≤2⋅10^5, s_i∈{W,A,S,D}) s(1≤∣s∣≤2⋅105,si∈W,A,S,D) — the sequence of commands.
It’s guaranteed that the total length of s s s over all queries doesn’t exceed 2 ⋅ 1 0 5 2⋅10^5 2⋅105.
Output
Print T T T integers: one per query. For each query print the minimum area of G r i d ( s ) Grid(s) Grid(s) you can achieve.
Example
Input
3
DSAWWAW
D
WA
Output
8
2
4
Note
In the first query you have to get string D S A W W { D } A W DSAWW\{D\}AW DSAWW{D}AW.
In second and third queries you can not decrease the area of G r i d ( s ) Grid(s) Grid(s).
題意：
給定一個字元串，四種字元分别表示上下左右
你可以在任意位置，最多插入1個字元，使得所經過的點，用一個最小的矩形包住，使得這個矩形的面積最小。
求最小面積。
題解：
枚舉插入位置，然後枚舉插入的字元。
我們可以知道，影響答案的隻跟maxx,maxy,minx,miny有關系
那麼我們維護字元串字首和字尾的這四個值，然後很顯然插入字元之後等于後面所有坐标向這個位置平移。
然後直接計算即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF=1e18;
int n;
int mx,my,gx,gy;
char s[200004];
int dx[4]={0,1,0,-1},
dy[4]={1,0,-1,0};
map<char,int>mp;
struct point{
int x,y;
point(int _x=0,int _y=0){x=_x;y=_y;}
point operator+(point B){
return point(x+B.x,y+B.y);
}
void print(){
printf("(%d,%d)",x,y);
}
}p[200004];
struct Ds{
int minx,miny,maxx,maxy;
Ds(int _a=0,int _b=0,int _c=0,int _d=0){
minx=_a;
miny=_b;
maxx=_c;
maxy=_d;
}
void Merge(Ds B){
minx=min(minx,B.minx);
miny=min(miny,B.miny);
maxx=max(maxx,B.maxx);
maxy=max(maxy,B.maxy);
}
void print(){
cout<<minx<<" "<<miny<<" "<<maxx<<" "<<maxy<<endl;
}
}tr[200004];
void update(int k){
tr[k].maxx=max(p[k].x,tr[k+1].maxx);
tr[k].minx=min(p[k].x,tr[k+1].minx);
tr[k].maxy=max(p[k].y,tr[k+1].maxy);
tr[k].miny=min(p[k].y,tr[k+1].miny);
}
void build(){
tr[n]=Ds(p[n].x,p[n].y,p[n].x,p[n].y);
for(int i=n-1;i>=0;i--){
update(i);
//tr[i].print();cout<<"--"<<endl;
}
}
Ds query(int k){
return tr[k];
}
ll calc(Ds v){
return 1LL*(v.maxx-v.minx+1)*(v.maxy-v.miny+1);
}
ll work(int st){
Ds Gc,left=Ds(gx,gy,mx,my);
//left.print();
Ds right=query(st);
ll res=-1;
for(int i=0;i<4;i++){
Gc=left;
Gc.Merge(Ds(right.minx+dx[i],right.miny+dy[i],right.maxx+dx[i],right.maxy+dy[i]));
Gc.Merge(Ds(p[st-1].x+dx[i],p[st-1].y+dy[i],p[st-1].x+dx[i],p[st-1].y+dy[i]));
//Gc.print();
ll now=calc(Gc);
if(res==-1||(res!=-1&&res>now)){
res=now;
}
}
//cout<<"qqqq"<<endl;
return res;
}
int w33ha(){
p[0]=point(0,0);
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++){
p[i]=p[i-1]+point(dx[mp[s[i]]],dy[mp[s[i]]]);
//p[i].print();
}
//puts("");
ll ans=INF;
build();
mx=p[0].x;
my=p[0].y;
gx=p[0].x;
gy=p[0].y;
for(int i=1;i<=n;i++){
ans=min(ans,work(i));
mx=max(mx,p[i].x);
my=max(my,p[i].y);
gx=min(gx,p[i].x);
gy=min(gy,p[i].y);
}
printf("%lld\n",ans);
return 0;
}
int main(){
mp['W']=3;
mp['D']=0;
mp['S']=1;
mp['A']=2;
int T;scanf("%d",&T);
while(T--)w33ha();
return 0;
}