Not able to solve the question

#1

sir i have tried this question alot now can you plz provide me with the code of this to get a better understandingā€¦ of this plzā€¦

#2

Hey @Shobhit_kumar
Letā€™s consider a single row that contains at least one black cell. If the first appearance of a black cell is at the l-th column and the last appearance of a black cell is at the r-th column, we can determine whether it becomes a white line when a certain cell (i,j) is clicked in O(1), after some preprocessing. It becomes a white line if and only if a cell (i,j) is clicked where the row is at [i,i+kāˆ’1] and jā‰¤lā‰¤rā‰¤j+kāˆ’1. We just need to compute l and r in advance.

Now letā€™s consider all n rows (not columns). First, count all rows that are already white lines before clicking. Then we count the number of white rows when the cell (1,1) is clicked, by applying the above method to all rows from 1 to k. Ignore the already-white rows that we counted before. So far we obtained the number of white rows when the cell (1,1) is clicked. From now, we slide the window. Add the k+1-st row and remove the 1-st row by applying the same method to them, and we obtain the number of white rows when the cell (2,1) is clicked. We can repeat this until we calculate all nāˆ’k+1 cases for clicking the cells at the 1-st column. Then we repeat the whole process for all nāˆ’k+1 columns.

The same process can be done for counting white columns, too. Now we know the number of white rows and white columns when each cell is clicked, so we can find the maximum value among their sums.

Time complexity: O(n2)

#include<bits/stdc++.h>
using namespace std;
int n,k,a[2003][2003],b[2003][2003],c[2003][2003],d[2003][2003],cnt,ans;
string s[2003];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]=' '+s[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			a[i][j]=a[i-1][j]+(s[i][j]=='B');
			b[i][j]=b[i][j-1]+(s[i][j]=='B');
		}


	for(int i=1;i<=n;i++)
		cnt+=(a[n][i]==0)+(b[i][n]==0);

	for(int i=k;i<=n;i++)
		for(int j=1;j<=n;j++)
			c[i][j]=c[i][j-1]+(a[i-k][j]==0&&a[n][j]-a[i][j]==0&&a[i][j]-a[i-k][j]>0);
	
	for(int i=1;i<=n;i++)
		for(int j=k;j<=n;j++)
			d[i][j]=d[i-1][j]+(b[i][j-k]==0&&b[i][n]-b[i][j]==0&&b[i][j]-b[i][j-k]>0);
	
	for(int i=k;i<=n;i++)
		for(int j=k;j<=n;j++)
			ans=max(ans,c[i][j]-c[i][j-k]+d[i][j]-d[i-k][j]);
			
	cout<<cnt+ans;	
}