Practice

# EXPLANATION:

Let dp(i,j) denote the maximum length of scam square you can make if the cell (i,j) is bottom and right most cell of that square.

If the square (i,j) , (i-1,j) , (i,j-1) and (i-1,j-1) doesn’t form a scam square, then dp(i,j) = 1. Otherwise, we can calculate dp(i,j) in O(1) by the value of dp(i-1,j) , dp(i,j-1) and dp(i-1,j-1).

As, dp(i,j) = min(dp(i-1,j),dp(i,j-1),dp(i-1,j-1))+1

The answer of the problem will be summation of dp(i,j) over all cells.

# SOLUTION:

Setter's Solution
``````    #include<bits/stdc++.h>
using namespace std;

int main(){

int T;
cin>>T;

while(T--){
int n;
cin>>n;
vector<string> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}

int dp[n][n];

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==0||j==0){
dp[i][j]=1;
}
else if(v[i][j]==v[i-1][j-1]&&v[i][j]!=v[i-1][j]&&v[i][j]!=v[i][j-1]){
dp[i][j] = min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}) + 1;
}
else{
dp[i][j] = 1;
}
}
}

long long ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ans+=dp[i][j];
}
}
cout<<ans<<"\n";
}

return 0;
}
``````
1 Like