Given a matrix mat[][], pair of indices X and Y, the task is to find the number of moves to bring all the non-zero elements of the matrix to the given cell at (X, Y).
A move consists of moving an element at any cell to its four directional adjacent cells i.e., left, right, top, bottom.
Examples:
Input: mat[][] = {{1, 0}, {1, 0}}, X = 1, Y = 1
Output: 3
Explanation:
Moves required =>
For Index (0, 0) => 2
For Index (1, 0) => 1
Total moves required = 3
Input: mat[][] = {{1, 0, 1, 0}, {1, 1, 0, 1}, {0, 0, 1, 0}}, X = 1, Y = 3
Output: 13
Approach: The idea is to traverse the matrix and for each non-zero element of the matrix find the distance of the current cell(say (A, B)) to the destination cell (X, Y) of the matrix as:
moves = abs(x - i) + abs(y - j)
The summation of all the distances by the above formula for all non-zero elements is the required result.
Below is the implementation of the above approach:
C++
// C++ implementation to find the// minimum number of moves to// bring all non-zero element// in one cell of the matrix#include <bits/stdc++.h>using namespace std;const int M = 4;const int N = 5;// Function to find the minimum// number of moves to bring all// elements in one cell of matrixvoid no_of_moves(int Matrix[M][N], int x, int y){ // Moves variable to store // the sum of number of moves int moves = 0; // Loop to count the number // of the moves for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // Condition to check that // the current cell is a // non-zero element if (Matrix[i][j] != 0) { moves += abs(x - i); moves += abs(y - j); } } } cout << moves << "\n";}// Driver Codeint main(){ // Coordinates of given cell int x = 3; int y = 2; // Given Matrix int Matrix[M][N] = { { 1, 0, 1, 1, 0 }, { 0, 1, 1, 0, 1 }, { 0, 0, 1, 1, 0 }, { 1, 1, 1, 0, 0 } }; // Element to be moved int num = 1; // Function call no_of_moves(Matrix, x, y); return 0;} |
Java
// Java implementation to find the// minimum number of moves to// bring all non-zero element// in one cell of the matrixclass GFG{ static int M = 4;static int N = 5;// Function to find the minimum// number of moves to bring all// elements in one cell of matrixpublic static void no_of_moves(int[][] Matrix, int x, int y){ // Moves variable to store // the sum of number of moves int moves = 0; // Loop to count the number // of the moves for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // Condition to check that // the current cell is a // non-zero element if (Matrix[i][j] != 0) { moves += Math.abs(x - i); moves += Math.abs(y - j); } } } System.out.println(moves);}// Driver codepublic static void main(String[] args){ // Coordinates of given cell int x = 3; int y = 2; // Given Matrix int[][] Matrix = { { 1, 0, 1, 1, 0 }, { 0, 1, 1, 0, 1 }, { 0, 0, 1, 1, 0 }, { 1, 1, 1, 0, 0 } }; // Element to be moved int num = 1; // Function call no_of_moves(Matrix, x, y);}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 implementation to find the# minimum number of moves to# bring all non-zero element# in one cell of the matrixM = 4N = 5# Function to find the minimum# number of moves to bring all# elements in one cell of matrixdef no_of_moves(Matrix, x, y): # Moves variable to store # the sum of number of moves moves = 0 # Loop to count the number # of the moves for i in range(M): for j in range(N): # Condition to check that # the current cell is a # non-zero element if (Matrix[i][j] != 0): moves += abs(x - i) moves += abs(y - j) print(moves)# Driver Codeif __name__ == '__main__': # Coordinates of given cell x = 3 y = 2 # Given Matrix Matrix = [ [ 1, 0, 1, 1, 0 ], [ 0, 1, 1, 0, 1 ], [ 0, 0, 1, 1, 0 ], [ 1, 1, 1, 0, 0 ] ] # Element to be moved num = 1 # Function call no_of_moves(Matrix, x, y)# This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the // minimum number of moves to // bring all non-zero element // in one cell of the matrix using System;class GFG{ static int M = 4; static int N = 5; // Function to find the minimum // number of moves to bring all // elements in one cell of matrix public static void no_of_moves(int[,] Matrix, int x, int y) { // Moves variable to store // the sum of number of moves int moves = 0; // Loop to count the number // of the moves for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // Condition to check that // the current cell is a // non-zero element if (Matrix[i, j] != 0) { moves += Math.Abs(x - i); moves += Math.Abs(y - j); } } } Console.WriteLine(moves); } // Driver code public static void Main(String[] args) { // Coordinates of given cell int x = 3; int y = 2; // Given matrix int[,] Matrix = { { 1, 0, 1, 1, 0 }, { 0, 1, 1, 0, 1 }, { 0, 0, 1, 1, 0 }, { 1, 1, 1, 0, 0 } }; // Function call no_of_moves(Matrix, x, y); } } // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation to find the// minimum number of moves to// bring all non-zero element// in one cell of the matrix let M = 4;let N = 5; // Function to find the minimum// number of moves to bring all// elements in one cell of matrixfunction no_of_moves(Matrix, x, y){ // Moves variable to store // the sum of number of moves let moves = 0; // Loop to count the number // of the moves for(let i = 0; i < M; i++) { for(let j = 0; j < N; j++) { // Condition to check that // the current cell is a // non-zero element if (Matrix[i][j] != 0) { moves += Math.abs(x - i); moves += Math.abs(y - j); } } } document.write(moves);}// Driver Code // Coordinates of given cell let x = 3; let y = 2; // Given Matrix let Matrix = [[ 1, 0, 1, 1, 0 ], [ 0, 1, 1, 0, 1 ], [ 0, 0, 1, 1, 0 ], [ 1, 1, 1, 0, 0 ]]; // Element to be moved let num = 1; // Function call no_of_moves(Matrix, x, y); </script> |
Output:
27
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
