Tuesday, 19 Oct 2021

# Find any possible two coordinates of Rectangle whose two coordinates are given

Given a matrix mat[][] of size N×N where two elements of the matrix are ‘1’ denoting the coordinate of the rectangle and ‘0’ denotes the empty space, the task is to find the other two coordinates of the rectangle.Note: There can be multiple answers possible for this problem, print any one of them.Examples: Input: mat[][] = {{0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}Output: {{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}}Explanation: 0 0 1 1 0 0 1 10 0 0 00 0 0 0The coordinates {{0, 2}, {0, 3}, {1, 2}, {1, 3}} forms the rectangleInput: mat[][] = {{0, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 0, 0}, {0, 0, 0, 0}} Output: {{1, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}}Approach: The remaining coordinate can be found using these given coordinates because some points may have a common row and some might have a common column. Follow the steps below to solve the problem:Initialize two pairs, say p1 and p2 to store the position of 1 in the initial matrix mat[].Initialize two pairs, say p3 and p4 to store position where new 1 is to be inserted to make it a rectangle.Traverse through the matrix using two nested loops and find the pairs p1 and p2.Now there are three possible cases:If p1.first and p2.first are same in this case adding 1 to p1.first and p2.first gives us p3.first and p4.first while p3.second and p4.second remain the same as p1.second and p2.second respectively.If p1.second and p2.second are the same in this case adding 1 to p1.second and p2.second gives us p3.second and p4.second while p3.first and p4.first remains the same as p1.first and p2.first If no coordinates are same, then p3.first = p2.first, p3.second = p1.second, p4.first = p1.first and p4.second = p2.second.Replace the coordinates of p3 and p4 with 1 and print the matrix.Below is the implementation of the above approach:C++  #include using namespace std;  void Create_Rectangle(vector arr, int n){              pair p1 = { -1, -1 };    pair p2 = { -1, -1 };              pair p3;    pair p4;              for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            if (arr[i][j] == '1')                if (p1.first == -1)                    p1 = { i, j };                else                    p2 = { i, j };        }    }      p3 = p1;    p4 = p2;          if (p1.first == p2.first) {        p3.first = (p1.first + 1) % n;        p4.first = (p2.first + 1) % n;    }        else if (p1.second == p2.second) {        p3.second = (p1.second + 1) % n;        p4.second = (p2.second + 1) % n;    }        else {        swap(p3.first, p4.first);    }      arr[p3.first][p3.second] = '1';    arr[p4.first][p4.second] = '1';          for (int i = 0; i < n; i++) {        cout