just contest finished and i see some of the solution but not getting intuition of the solution could you guys help ?
It is a dp question find out the no. of squares ending at a given i,j.
It should be min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
if(s[i][j] and s[i-1][j-1] are same and s[i-1][j] and s[i][j-1] are same and s[i][j] and s[i-1][j] are not same.
else dp[i][j]=1;
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double ld;
/*
#include <chrono>
using namespace std::chrono;
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<lli, null_type,less_equal<lli>, rb_tree_tag,tree_order_statistics_node_update>
//remove _equal from less_equal to make it ordered set , currently it is ordered_multiset
*/
#define endl "\n"
#define pb push_back
const lli mod=1e9+7;
const lli mod1=998244353;
#define fir first
#define sec second
#define plli pair<lli,lli>
#define pplli pair<lli,plli>
/*
lli power(lli a, lli b) {
lli res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
lli powermod(lli a, lli b)
{
lli res = 1;
while (b > 0) {
if (b & 1)
res = ((res%mod)*(a%mod))%mod;
a = (a * a)%mod;
b >>= 1;
}
return res%mod;
}
*/
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli T,i,j,k,t;
T=1;
cin>>T;
while(T--)
{
lli n;
cin>>n;
string s[n];
for(i=0;i<n;i++)
{
cin>>s[i];
}
lli dp[n][n];
for(i=0;i<n;i++)
{
dp[0][i]=1;
dp[i][0]=1;
}
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1]);
if((s[i][j]==s[i-1][j-1])and(s[i-1][j]==s[i][j-1])and(s[i][j]!=s[i-1][j]))
dp[i][j]++;
else
dp[i][j]=1;
}
}
lli ans=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
ans+=dp[i][j];
}
}
cout<<ans<<"\n";
}
return 0;
}
3 Likes