# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### 题解 CF1202C 【You Are Given a WASD-string...】

posted on 2019-08-15 20:56:39 | under 题解 |

#define MAXN 200010
#define LL long long
#define Inf 192608170

using namespace std ; LL ans ;
int fhm, fhn, fwm, fwn, pos[2][5], i ;
int T, N, Sw[MAXN], Sh[MAXN] ; char S[MAXN] ;

int main(){
cin >> T ;
while (T --){
fhm = fwm = -Inf, fhn = fwn = Inf ;
scanf("%s", S + 1), N = strlen(S + 1) ;
for (i = 1 ; i <= N ; ++ i){
Sh[i] = Sh[i - 1], Sw[i] = Sw[i - 1] ;
if (S[i] == 'W') Sh[i] = Sh[i - 1] + 1 ;
else if (S[i] == 'S') Sh[i] = Sh[i - 1] - 1 ;
else if (S[i] == 'D') Sw[i] = Sw[i - 1] + 1 ;
else if (S[i] == 'A') Sw[i] = Sw[i - 1] - 1 ;
}//前缀和 : w x h
for (i = 0 ; i <= N ; ++ i) fwm = max(Sw[i], fwm), fwn = min(Sw[i], fwn) ;
for (i = 0 ; i <= N ; ++ i) fhm = max(Sh[i], fhm), fhn = min(Sh[i], fhn) ;
for (i = N ; ~i ; -- i) if (Sh[i] == fhn) { pos[0][4] = i ; break ; } //last_min h
for (i = N ; ~i ; -- i) if (Sw[i] == fwn) { pos[1][4] = i ; break ; } //last_min h
for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhm) { pos[0][1] = i ; break ; }  //first_max h
for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwm) { pos[1][1] = i ; break ; }  //first_max w

for (i = N ; ~i ; -- i) if (Sh[i] == fhm) { pos[0][3] = i ; break ; } //last_max h
for (i = N ; ~i ; -- i) if (Sw[i] == fwm) { pos[1][3] = i ; break ; } //last_max h
for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhn) { pos[0][2] = i ; break ; }  //first_min h
for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwn) { pos[1][2] = i ; break ; }  //first_min w
ans = 1ll * (fwn - fwm - 1) * (fhn - fhm - 1) ; //cout << ans << endl ;
if (pos[0][3] < pos[0][2] && Sh[pos[0][3]] - Sh[pos[0][2]] > 1)
ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ;
if (pos[1][3] < pos[1][2] && Sw[pos[1][3]] - Sw[pos[1][2]] > 1)
ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ;
if (pos[0][4] < pos[0][1] && Sh[pos[0][4]] - Sh[pos[0][1]] < -1)
ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ;
if (pos[1][4] < pos[1][1] && Sw[pos[1][4]] - Sw[pos[1][1]] < -1)
ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ;
cout << ans << endl ;
pos[0][1] = pos[1][1] = pos[0][2] = pos[1][2] = Inf ;
pos[0][3] = pos[1][3] = pos[0][4] = pos[1][4] = -Inf ;
}
}