Minimize the number of iterations to Fill a Matrix with Ones
Given a matrix with dimensions N x M, filled with zeroes except for one position at coordinates X and Y containing ‘1’. In one iteration, ‘1’ can be filled in the 4 neighboring elements of a cell containing ‘1’. This means if there are 2 cells with ‘1’, their neighboring cells can be marked as ‘1’ in the next iteration. Find the minimum number of iterations in which the whole matrix can be filled with ones.
Note: The matrix follows 1-based indexing. This means the coordinates of the starting point will be in 1-based indexing.
Examples:
Input: N = 2, M = 3, X = 2, Y = 3
Output: 3
Explanation:Input: N = 5, M = 10, X = 4, Y = 6
Output: 8
Approach Using Manhattan Distance:
- The first thing that we need to realize is that the number of iterations depends on the distance of the farthest cell from {x,y}. We just need to find the minimum steps needed to reach that farthest cell. The minimum steps required to go from one cell to another equal the Manhattan distance between them. This is given by |A-X| + |B-Y|.
- Now we just need to identify the farthest cell. For this, we need to realize that, the farthest cell will be one of the four corners. Any cell other than the corners will be closer than the corner itself. Now since we don’t know our initial location, i.e. {x, y} can be anything, we need to find the Manhattan distance to all four corners and find the maximum out of them.
Steps to implement:
- The coordinates of the four corners are (1, 1), (1, N), (1, M) and (N, M).
- Find the Manhattan Distance from the given origin to all four corners.
- The maximum distance among them is minimum iterations required to fill the whole matrix.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int getDistance( int dx, int dy, int x, int y) { // Finding Manhattan distance between // (dx,dy) and (x,y) return abs (dx - x) + abs (dy - y); } int minIteration( int N, int M, int x, int y) { return max(max(getDistance(1, 1, x, y), getDistance(1, M, x, y)), max(getDistance(N, 1, x, y), getDistance(N, M, x, y))); } // Drivers code int main() { int n = 3, m = 3, x = 1, y = 1; // Function Call cout << minIteration(n, m, x, y); return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { public static int getDistance( int dx, int dy, int x, int y) { // Finding Manhattan distance between (dx,dy) and // (x,y) return Math.abs(dx - x) + Math.abs(dy - y); } public static int minIteration( int N, int M, int x, int y) { return Math.max(Math.max(getDistance( 1 , 1 , x, y), getDistance( 1 , M, x, y)), Math.max(getDistance(N, 1 , x, y), getDistance(N, M, x, y))); } // Driver code public static void main(String[] args) { int n = 3 , m = 3 , x = 1 , y = 1 ; // Function Call System.out.println(minIteration(n, m, x, y)); } } |
Python3
# Function to calculate Manhattan distance between two points def get_distance(dx, dy, x, y): # Finding Manhattan distance between (dx,dy) and (x,y) return abs (dx - x) + abs (dy - y) # Function to find the maximum distance of point (x, y) from the corners of the grid def min_iteration(N, M, x, y): # Calculating distances from each corner to point (x, y), # taking maximum distance among all corners return max ( max (get_distance( 1 , 1 , x, y), # Distance from top-left corner get_distance( 1 , M, x, y)), # Distance from top-right corner max (get_distance(N, 1 , x, y), # Distance from bottom-left corner get_distance(N, M, x, y)) # Distance from bottom-right corner ) # Driver code if __name__ = = "__main__" : n, m, x, y = 3 , 3 , 1 , 1 # Function Call to find minimum iteration for point (x, y) print (min_iteration(n, m, x, y)) |
C#
using System; class GFG { // Function to calculate the Manhattan distance between // two points (dx, dy) and (x, y) static int GetDistance( int dx, int dy, int x, int y) { return Math.Abs(dx - x) + Math.Abs(dy - y); } // Function to find the minimum iteration to // reach the farthest corner static int MinIteration( int N, int M, int x, int y) { return Math.Max(Math.Max(GetDistance(1, 1, x, y), GetDistance(1, M, x, y)), Math.Max(GetDistance(N, 1, x, y), GetDistance(N, M, x, y))); } // Driver code static void Main() { int n = 3, m = 3, x = 1, y = 1; // Function Call Console.WriteLine(MinIteration(n, m, x, y)); } } |
Javascript
function getDistance(dx, dy, x, y) { return Math.abs(dx - x) + Math.abs(dy - y); // Finding Manhattan distance } function minIteration(N, M, x, y) { return Math.max( Math.max(getDistance(1, 1, x, y), getDistance(1, M, x, y)), Math.max(getDistance(N, 1, x, y), getDistance(N, M, x, y)) ); } const n = 3, m = 3, x = 1, y = 1; console.log(minIteration(n, m, x, y)); |
4
Time Complexity: O(1).
Auxiliary Space: O(1).