This is the link of problem: D. White Line.
For the best i understand up to now, let's focus on row.
I will base on the range [l;r] each row of black to determine whether which cells that we click will erase this row or not. These cells are in the rectangle from $$$(l1, l2)$$$ (top left) to $$$(r1-1, r2-1)$$$ (bottom right), $$$l1, l2, r1, r2$$$ is defined in the code i extracted from @kcm1770's solution.
for(int i=0; i<n; ++i) {
int l=0;
while(l<n&&s[i][l]=='W')
++l;
if(l>=n) {
++b[0][0];
continue;
}
int r=n-1;
while(~r&&s[i][r]=='W')
--r;
if(r-l+1>k)
continue;
//i-k+1, i
//r-k+1, l
int l1=max(i-k+1, 0), r1=i+1;
int l2=max(r-k+1, 0), r2=l+1;
++b[l1][l2];
--b[l1][r2];
--b[r1][l2];
++b[r1][r2];
}
I see a lot of people do the same approach. I don't know how they come up with the way set ++ & -- like that. This is all of magic for me. Could you tell me about some similar problems using that or some concepts involve.
I solved the problem using the approach that was given in the editorial. Here is my code: 58682265 I added comments for clarity. I hope this will help you.
thank you very much. Your code looks so easy to read.
Not really related, but as a trick to avoid typos / reduce coding, you can write a helper function to compute the answer for only the rows, then call it on the transposed array to get the answer for columns. (Example: 58636000)
It's really easy to make mistakes when rewriting a whole block of code switching rows & columns, otherwise.
It’s very nice.