Minimum steps to get 1 at the center of a binary matrix
Given an N * N matrix where N is odd with all 0 values except for a single cell which has the value 1. The task is to find the minimum possible moves to get this 1 to the center of the matrix when in a single move, any two consecutive rows or two consecutive columns can be swapped.
Examples:
Input: mat[][] = {
{0, 0, 1, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}}
Output: 2
Operation 1: Swap the first and the second row.
Operation 2: Swap the second and the third row.
Input: mat[][] = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}}
Output: 0
Approach:
- Calculate the position of the center of the matrix as (cI, cJ) = (?N / 2?, ?N / 2?).
- Find the position of the 1 in the matrix and store it in (oneI, oneJ).
- Now, the minimum possible moves will be abs(cI – oneI) + abs(cJ – oneJ).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; const int N = 5; // Function to return the // minimum moves required int minMoves( int mat[N][N]) { // Center of the matrix int cI = N / 2, cJ = N / 2; // Find the position of the 1 int oneI = 0, oneJ = 0; for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { if (mat[i][j] == 1) { oneI = i; oneJ = j; break ; } } } return ( abs (cI - oneI) + abs (cJ - oneJ)); } // Driver code int main() { int mat[N][N] = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0 } }; cout << minMoves(mat); return 0; } |
Java
// Java implementation of the approach class GFG { static int N = 5 ; // Function to return the // minimum moves required static int minMoves( int mat[][]) { // Center of the matrix int cI = N / 2 , cJ = N / 2 ; // Find the position of the 1 int oneI = 0 , oneJ = 0 ; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { if (mat[i][j] == 1 ) { oneI = i; oneJ = j; break ; } } } return (Math.abs(cI - oneI) + Math.abs(cJ - oneJ)); } // Driver code public static void main(String[] args) { int mat[][] = { { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 1 , 0 , 0 } }; System.out.print(minMoves(mat)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach N = 5 # Function to return the # minimum moves required def minMoves(mat): # Center of the matrix cI = N / / 2 cJ = N / / 2 # Find the position of the 1 oneI = 0 oneJ = 0 for i in range (N): for j in range (N): if (mat[i][j] = = 1 ): oneI = i oneJ = j break return ( abs (cI - oneI) + abs (cJ - oneJ)) # Driver code mat = [[ 0 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 1 , 0 , 0 ]] print (minMoves(mat)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { static int N = 5; // Function to return the // minimum moves required static int minMoves( int [,]mat) { // Center of the matrix int cI = N / 2, cJ = N / 2; // Find the position of the 1 int oneI = 0, oneJ = 0; for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { if (mat[i, j] == 1) { oneI = i; oneJ = j; break ; } } } return (Math.Abs(cI - oneI) + Math.Abs(cJ - oneJ)); } // Driver code public static void Main(String[] args) { int [,]mat = {{ 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0 }}; Console.Write(minMoves(mat)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the approach const N = 5; // Function to return the // minimum moves required function minMoves(mat) { // Center of the matrix let cI = parseInt(N / 2), cJ = parseInt(N / 2); // Find the position of the 1 let oneI = 0, oneJ = 0; for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { if (mat[i][j] == 1) { oneI = i; oneJ = j; break ; } } } return (Math.abs(cI - oneI) + Math.abs(cJ - oneJ)); } // Driver code let mat = [ [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ] ]; document.write(minMoves(mat)); </script> |
Output:
2
Time Complexity: O(N^2)
Auxiliary Space Complexity: O(1)