<p>You are given two images, <code>img1</code> and <code>img2</code>, represented as binary, square matrices of size <code>n x n</code>. A binary matrix has only <code>0</code>s and <code>1</code>s as values.</p>

<p>We <strong>translate</strong> one image however we choose by sliding all the <code>1</code> bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the <strong>overlap</strong> by counting the number of positions that have a <code>1</code> in <strong>both</strong> images.</p>

<p>Note also that a translation does <strong>not</strong> include any kind of rotation. Any <code>1</code> bits that are translated outside of the matrix borders are erased.</p>

<p>Return <em>the largest possible overlap</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/09/overlap1.jpg" style="width: 450px; height: 231px;" />
<pre>
<strong>Input:</strong> img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We translate img1 to right by 1 unit and down by 1 unit.
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/09/overlap_step1.jpg" style="width: 450px; height: 105px;" />
The number of positions that have a 1 in both images is 3 (shown in red).
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/09/overlap_step2.jpg" style="width: 450px; height: 231px;" />
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> img1 = [[1]], img2 = [[1]]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> img1 = [[0]], img2 = [[0]]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == img1.length == img1[i].length</code></li>
	<li><code>n == img2.length == img2[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 30</code></li>
	<li><code>img1[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
	<li><code>img2[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
    
    int help(vector<vector<int>>&img1,vector<vector<int>>&img2, int r, int c)
    {
        int n = img1.size(), count = 0;
        
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i+r<0 || i+r>=n || j+c<0 || j+c>= n)
                {
                    continue;
                }
                
                if(img1[i][j] + img2[i+r][j+c] == 2)
                {
                    count++;
                }
            }
        }
        
        return count;
    }            
    
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) 
    {
        
        int n = img1.size(),ans = 0;
        
        for(int i= -n+1; i<n; i++)
        {
            for(int j= -n+1; j<n; j++)
            {
                ans = max(ans, help(img1,img2,i,j));
            }
        }
        
        return ans;
        
         /*https://www.youtube.com/watch?v=Jzs2_6qf78c*/
        
        //O(n^4)
    }
};
/*
I see the confusion. Let me clarify:

When both i and j are negative, it doesn't necessarily mean img2 is shifted to the left and upward relative to img1. Similarly, when both i and j are positive, it doesn't necessarily mean img2 is shifted to the right and downward relative to img1.

Rather, the signs of i and j determine the direction and magnitude of the shift of img2 relative to img1. Let's correct that:

Negative i and j:
When both i and j are negative, it means img2 is shifted to the left and upward relative to img1. For example, i = -1 and j = -1 would mean img2 is shifted one position to the left and one position upward relative to img1.
Positive i and j:
When both i and j are positive, it means img2 is shifted to the right and downward relative to img1. For example, i = 1 and j = 1 would mean img2 is shifted one position to the right and one position downward relative to img1.
Combination of Signs:
When one of i or j is negative and the other is positive, it indicates a diagonal shift of img2 relative to img1. For example, if i = -1 and j = 1, it means img2 is shifted one position to the left and one position downward relative to img1, resulting in a diagonal shift.
By iterating over all possible combinations of i and j, the code explores all potential positions of img2 relative to img1, including horizontal, vertical, and diagonal shifts. This approach ensures that the code considers all possible overlaps between img1 and img2, allowing it to find the largest overlap.*/
12300