1366C. Palindromic Paths - Codeforces Solution C++

➤  Problem Link : 1366C. Palindromic Paths 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		int arr[n][m];
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				cin>>arr[i][j];

		int ans=0,i1=0,j1=0,i2=n-1,j2=m-1,total,oneCount;
		int a1,a2,b1,b2;
		while(i1!=i2 || j1!=j2)
		{
		    
			total=0;
			oneCount=0;
			a1=i1;
			a2=j1;
			b1=i2;
			b2=j2;
			while(a2>=0 && b2>=0 && a1<n && b1<n)
			{
				total+=2;
				if(arr[a1][a2]==1)
					oneCount++;
				if(arr[b1][b2]==1)
					oneCount++;
				a1++;
				a2--;
				b2--;
				b1++;
			}

			if(oneCount*2>total)
				ans+=total-oneCount;
			else
				ans+=oneCount;
			
			if(i2==0 && j2==j1+1)
			    break;
			
			if(j1==m-1 && i1==i2-1)
			    break;
				
			if(j1==m-1)
			    i1++;
			else
			    j1++;
			
			if(i2==0)
			    j2--;
			else
			    i2--;

		}	
		cout<<ans<<endl;

	}


}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.