1461B - Find the Spruce I started counting from the bottom row and counted three columns at once.Once you look at the code you will get the solution which is not that hard.
include<bits/stdc++.h>
include<conio.h>
include<time.h>
using namespace std;
define ll long long int
define vi vector
define pr pair<ll,ll>
define bs(n) bitset
define pi acos(-1)
define pb push_back
define pop pop_back
define mp make_pair
define out(v); for(ll i=0;i<v.size();i++) cout<<v[i]<<" ";
define all(x) (x).begin(),(x).end()
define loop(i,a,n) for(ll i=a;i<n;i++)
define YES cout<<"YES"<<endl
define NO cout<<"NO"<<endl
define br; cout<<endl;
define point(a) fixed<<setprecision(a)
define MIN 0
define MAX 999999999999999999
inline ll LCM(ll x,ll y){ll m=max(x,y);while(1){ if(m%x==0 && m%y==0){return m;break;} else m++;}} inline ll GCD(ll x,ll y) {ll p=max(x,y);ll q=min(x,y); while(q){p%=q;swap(p,q);}return p;} //////////**********SET SAIL**********\\\\\
void solve(); int main() { solve(); return 0; } void solve() { ll t; cin>>t; while(t--) { int arr[600][600],sum=0; char a; int m,n; cin>>n>>m; loop(i,0,n) { loop(j,0,m) { cin>>a; if(a=='*') arr[i][j]=1; else arr[i][j]=0; } } for(int i=n-1;i>0;i--) { for(int j=m-1;j>=2;j--) { if(arr[i-1][j-1]==1) { arr[i-1][j-1]+=min(arr[i][j],min(arr[i][j-1],arr[i][j-2])); } } } loop(i,0,n) { loop(j,0,m) sum+=arr[i][j]; } cout<<sum<<endl; } }