Programming Skills: Image overlap

[Problem]
https://leetcode.com/problems/image-overlap/

Two images 'A' and 'B' are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 1:

Input: A = [[1,1,0],
                  [0,1,0],
                  [0,1,0]]
           B = [[0,0,0],
                  [0,1,1],
                  [0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

Notes:
1. 1 <= A.length = A[0].length = B.length = B[0].length <= 30
2. 0 <= A[i][j], B[i][j] <= 1

中文翻譯:

給兩個正方形二維陣列A and B，裡面的值是1 or 0。

我們可以上下左右移動A，接著將A貼合到B的上面。
如果貼合時A and B同一位置中的元素都是1，就得一分。

請問所有可能的情況中(A可以上下左右移動會有很多情況)

最高得分會是多少?

舉例來說:

上例中，若將A右一格再下移一格

貼合時能得3分，是最好的情況

所以return 3

[Solution]

Step 1: For all '1' in A, find and record all the movements which we can get score from it.

Input: A = [[1,1,0],
                  [0,0,0],
                  [0,0,0]]
           B = [[0,0,0],
                  [0,1,1],
                  [0,0,1]]

For Red '1' on A(0,0).
We can score from one of these movements: (+1,+1) or (+1,+2) or (+2,+2)
For Blue '1' on A(0,1).
We can score from one of these movements: (+1,+0) or (+1,+1) or (+2,+1)

Step 2: For all movements found in step1, find the one who scores most. Return the score.

There are 5 unique movements in step1: (+1,+1) / (+1,+2) / (+2,+2) / (+1,+0) / (+2,+1)

Among them, "(+1,+1)" scores most.

(Because it makes both Red '1' and Blue '1' score)

Return the score.

Finish.

[Implement]

There are some tricks in implementation:
1.We transform "movements" to "integers":
(delta R, delta C) ---> delta R*100 + delta C
(+3,-2) --> 3*100 - 2
2.We use the interger(represent movement) as the hashkey
And use hash table unordered_map<int, score> to record score of movement.

Of course there is another way, such as using 'String' as the hashkey.
Then use hash table unordered_map<string, score> to record score of movement.


    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
        //record the coordinate of all the '1' in A
        //record the coordinate of all the '1' in B
        vector<pair<int,int>> A1;
        vector<pair<int,int>> B1;
        for(int r=0;r<A.size();r++)
            for(int c=0;c<A[0].size();c++){
                if(A[r][c]==1)  A1.push_back(pair<int,int>(r,c));
                if(B[r][c]==1)  B1.push_back(pair<int,int>(r,c));
            }
        

        //Step1: For all '1' in A, find all the movements which we can get score from it.
        unordered_map<int, int> ht;
        for(auto ca:A1){
            for(auto cb:B1){
                int hashkey=(ca.first-cb.first)*100
                    +(ca.second-cb.second);
                ht[hashkey]++;
            }
        }
        
        //Step 2: For all movements found in step1, find the one who scores most. Return the score.
        int ans=0;
        for(auto it:ht){
            ans = max(ans,it.second);            
        }
        
        return ans;
    }