 # BOB AND SQUARES

Author: @somashekhar001
Tester: @somashekhar001
Editorialist: @somashekhar001

MEDIUM

# PREREQUISITES:

DYNAMIC-PROGRAMMING

# PROBLEM:

you have to cut a rectangle shaped glass to square shaped glasses till no rectangle shaped glass will left in minimum cuts.

# EXPLANATION:

consider a rectangle a × b if a=b then it is a square no need to cut ( 0 cuts ) else we need to make cut either horizontally or vertically .assume we make it horizontally ,then we can cut at any position 1,2,…,b-1.if we cut at position k ,we left with 2 pieces a × k and a × b-k then we can look up the number of moves to reduce these squares in the dp array we loop over all possibilities k and take the best one .similarly for vertical cuts.

The complexity is O(a^2 * b + a * b^2).

# SOLUTIONS:

`````` #include<bits/stdc++.h>

using namespace std;

int solve(int a,int b)

{

// creation of dp array for saving minimum number of cuts.

int dp[a+1][b+1];

for(int i=0;i<=a;i++) {
for(int j=0;j<=b;j++){
// if condition is for squares with 0 cuts.

if(i==j) {
dp[i][j]=0;
}
else{

dp[i][j]=1e4;
// traversing the all possibilities of horizontal cuts and saving which is optimal.
for(int k=1;k<i;k++){
dp[i][j]=min(dp[i][j],1+dp[i-k][j]+dp[k][j]);
}
// traversing the all possibilities  of vertical cuts and saving which is optimal.
for(int k=1;k<j;k++){
dp[i][j]=min(dp[i][j],1+dp[i][j-k]+dp[i][k]);
}

}

}
}
// returning  the optimal cuts needed to cut rectangle a × b.
return dp[a][b];
}
int main()
{
int a,b,t,ans;cin>>t;
while(t--){
cin>>a>>b;
ans=solve(a,b);
cout<<ans<<endl;
}
return 0;
}``````