SCMLD - Editorial

editorial
,
1

PROBLEM LINK:

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