PROBLEM LINK:
Author: Ayush Kumar Shukla
Tester: Shubham Gupta
Editorialist: Ayush Kumar Shukla
DIFFICULTY:
EASY
PREREQUISITES:
NONE
PROBLEM:
Given a string of letters 'L','R','U','D' where each letter represent one unit left, right, up, down step respectively. Given that this string of steps make a closed loop , you have to find the area of the loop formed by traversing it.
EXPLANATION:
We have to find the sum of all the vertical blocks formed in the loop. And by observation we can easily find that for each vertical block if the step at top is left then the step at bottom will be right and vice versa. So for each x in X axis,if we encounter a left or right step we keep the height at which the step occur. Now for each x in X axis, we sort the value of heights for the left and right steps. Now for each left step from x+1 to x, we have a right step from x to x+1 which makes a close vertical block or vice versa.
So starting from the first left and right step, we take summation of absolute difference of hieght i_{th} left and i_{th} right step for all the x in X axis.
This will give the total area inside the loop.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
main(){
ll t;
cin>>t;
while(t–)
{
string s;
cin>>s;
ll x=0,y=0;
ll minx=INT_MAX,maxx=INT_MIN;
map<ll,vector > left;
map<ll,vector > right;
for(ll i=0;i<s.length();i++){
if(s[i]==‘L’){
x–;
left[x].push_back(y);
}
if(s[i]==‘R’){
right[x].push_back(y);
x++;
}
if(s[i]=='U'){
y++;
}
if(s[i]=='D'){
y--;
}
if(minx>x){
minx = x;
}
if(maxx<x){
maxx=x;
}
}
ll area=0;
for(ll i = minx;i<=maxx;i++){
sort(left[i].begin(),left[i].end());
sort(right[i].begin(),right[i].end());
for(ll j=0;j<left[i].size();j++){
area+=abs(left[i][j]-right[i][j]);
}
}
cout<<area<<"\n";
}
}