İkili bir matriste 1 olan en yakın hücrenin mesafesi
GfG Practice'de deneyin 
Çıkış
Çıkış
Verilen bir ikili ızgara[][] . En yakın mesafeyi bulun 1 her hücre için ızgarada.
Mesafe şu şekilde hesaplanır: |ben 1 - Ben 2 | + |j 1 - J 2 | neredeyim 1 J 1 geçerli hücrenin satır numarası ve sütun numarasıdır ve i 2 J 2 1 değerine sahip en yakın hücrenin satır numarası ve sütun numarasıdır.
Not: Izgarada değeri 1 olan en az bir hücre bulunmalıdır.
Örnekler:
Giriş: ızgara[][] = [[0 1 1 0]
[1 1 0 0]
[0 0 1 1]]
Çıkış: [[1 0 0 1]
[0 0 1 1]
[1 1 0 0]]
Açıklama:
(0 1) hücresi, (0 0) hücresinde en yakın 1'e sahiptir - mesafe = |0-0| + |0-1| = 1
(0 2) hücresi (0 3) hücresinde en yakın 1'e sahiptir - mesafe = |0-0| + |3-2| = 1
(1 0) hücresi (0 0) hücresinde en yakın 1'e sahiptir - mesafe = |1-0| + |0-0| = 1
(1 1) hücresi, (1 2) hücresinde en yakın 1'e sahiptir - mesafe = |1-1| + |1-2| = 1
(2 2) hücresi, (2 1) hücresinde en yakın 1'e sahiptir - mesafe = |2-2| + |2-1| = 1
(2 3) hücresi (1 3) hücresinde en yakın 1'e sahiptir - mesafe = |2-1| + |3-3| = 1
Geri kalanların tümü 1'e sahip hücrelerdir, dolayısıyla en yakın 1'e sahip hücreye olan mesafeleri 0'dır.Giriş: ızgara[][] = [[1 0 1]
[1 1 0]
[1 0 0]]
Çıkış: [[0 1 0]
[0 0 1]
[0 1 2]]
Açıklama:
(0 0) hücresi (0 1) hücresinde en yakın 1'e sahiptir - mesafe = |0-0| + |0-1| = 1
(0 2) hücresi (0 1) hücresinde en yakın 1'e sahiptir - mesafe = |0-0| + |2-1| = 1
(1 0) hücresi (0 1) hücresinde en yakın 1'e sahiptir - mesafe = |1-0| + |0-1| = 2
(1 1) hücresi, (1 2) hücresinde en yakın 1'e sahiptir - mesafe = |1-1| + |1-2| = 1
(2 0) hücresi, (2 1) hücresinde en yakın 1'e sahiptir - mesafe = |2-2| + |2-1| = 1
(2 2) hücresi, (2 1) hücresinde en yakın 1'e sahiptir - mesafe = |2-2| + |2-1| = 1
Geri kalanların tümü 1'e sahip hücrelerdir, dolayısıyla en yakın 1'e sahip hücreye olan mesafeleri 0'dır.
İçerik Tablosu
- [Naif Yaklaşım] - O((n*m)^2) Zaman ve O(n * m) Uzay
- [Beklenen Yaklaşım] - Önce Genişlik Aramasını Kullanma - O(n * m) Zaman ve O(n * m) Uzay
[Naif Yaklaşım] - O((n*m)^2) Zaman ve O(n * m) Uzay
C++Buradaki fikir tüm ızgarayı geçmek ve her hücrenin en yakın 1'e olan mesafesini hesaplamaktır:
- Hücre 1 içeriyorsa mesafesi 0'dır.
- Hücre 0 içeriyorsa, 1 içeren en yakın hücreyi bulmak için tüm ızgarayı dolaşıyoruz.
- Her 0 hücre için Manhattan'ın tüm hücrelere olan uzaklığını 1 ile hesaplayın ve minimum mesafeyi alın.
Bu minimum mesafeyi sonuç matrisinin karşılık gelen hücresinde saklayın. Izgaradaki tüm hücreler için tekrarlayın.
//Driver Code Starts #include #include #include using namespace std ; //Driver Code Ends vector < vector < int >> nearest ( vector < vector < int >> & grid ) { int n = grid . size (); int m = grid [ 0 ]. size (); vector < vector < int >> ans ( n vector < int > ( m INT_MAX )); // visit each cell of the grid for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if the cell has 1 // then the distance is 0 if ( grid [ i ][ j ] == 1 ) { ans [ i ][ j ] = 0 ; continue ; } // iterate over all the cells // and find the distance of the nearest 1 for ( int k = 0 ; k < n ; k ++ ) { for ( int l = 0 ; l < m ; l ++ ) { if ( grid [ k ][ l ] == 1 ) { ans [ i ][ j ] = min ( ans [ i ][ j ] abs ( i - k ) + abs ( j - l )); } } } } } return ans ; } //Driver Code Starts int main () { vector < vector < int >> grid = {{ 0 1 1 0 } { 1 1 0 0 } { 0 0 1 1 }}; vector < vector < int >> ans = nearest ( grid ); for ( int i = 0 ; i < ans . size (); i ++ ) { for ( int j = 0 ; j < ans [ i ]. size (); j ++ ) { cout < < ans [ i ][ j ] < < ' ' ; } cout < < endl ; } return 0 ; } //Driver Code Ends
Java //Driver Code Starts import java.util.ArrayList ; class GFG { //Driver Code Ends static ArrayList < ArrayList < Integer >> nearest ( int [][] grid ) { int n = grid . length ; int m = grid [ 0 ] . length ; ArrayList < ArrayList < Integer > > ans = new ArrayList <> (); // initialize all cells with maximum value for ( int i = 0 ; i < n ; i ++ ) { ArrayList < Integer > row = new ArrayList <> (); for ( int j = 0 ; j < m ; j ++ ) { row . add ( Integer . MAX_VALUE ); } ans . add ( row ); } // visit each cell of the grid for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if the cell has 1 distance is 0 if ( grid [ i ][ j ] == 1 ) { ans . get ( i ). set ( j 0 ); continue ; } // iterate over all cells to find nearest 1 for ( int k = 0 ; k < n ; k ++ ) { for ( int l = 0 ; l < m ; l ++ ) { if ( grid [ k ][ l ] == 1 ) { int distance = Math . abs ( i - k ) + Math . abs ( j - l ); if ( distance < ans . get ( i ). get ( j )) { ans . get ( i ). set ( j distance ); } } } } } } return ans ; } //Driver Code Starts public static void main ( String [] args ) { int [][] grid = { { 0 1 1 0 } { 1 1 0 0 } { 0 0 1 1 } }; ArrayList < ArrayList < Integer > > ans = nearest ( grid ); for ( ArrayList < Integer > row : ans ) { for ( Integer val : row ) { System . out . print ( val + ' ' ); } System . out . println (); } } } //Driver Code Ends
Python def nearest ( grid ): n = len ( grid ) m = len ( grid [ 0 ]) ans = [[ float ( 'inf' )] * m for _ in range ( n )] # visit each cell of the grid for i in range ( n ): for j in range ( m ): # if the cell has 1 # then the distance is 0 if grid [ i ][ j ] == 1 : ans [ i ][ j ] = 0 continue # iterate over all the cells # and find the distance of the nearest 1 for k in range ( n ): for l in range ( m ): if grid [ k ][ l ] == 1 : ans [ i ][ j ] = min ( ans [ i ][ j ] abs ( i - k ) + abs ( j - l )) return ans #Driver Code Starts if __name__ == '__main__' : grid = [[ 0 1 1 0 ] [ 1 1 0 0 ] [ 0 0 1 1 ]] ans = nearest ( grid ) for i in range ( len ( ans )): for j in range ( len ( ans [ i ])): print ( ans [ i ][ j ] end = ' ' ) print () #Driver Code Ends
C# //Driver Code Starts using System ; using System.Collections.Generic ; class GfG { //Driver Code Ends static List < List < int > > nearest ( int [ ] grid ) { int n = grid . GetLength ( 0 ); int m = grid . GetLength ( 1 ); List < List < int > > ans = new List < List < int > > (); for ( int i = 0 ; i < n ; i ++ ) { List < int > row = new List < int > (); for ( int j = 0 ; j < m ; j ++ ) { row . Add ( int . MaxValue ); } ans . Add ( row ); } // Visit each cell of the grid for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // If the cell has 1 distance is 0 if ( grid [ i j ] == 1 ) { ans [ i ][ j ] = 0 ; continue ; } // iterate over all the cells // and find the distance of the nearest 1 for ( int k = 0 ; k < n ; k ++ ) { for ( int l = 0 ; l < m ; l ++ ) { if ( grid [ k l ] == 1 ) { int distance = Math . Abs ( i - k ) + Math . Abs ( j - l ); if ( distance < ans [ i ][ j ]) { ans [ i ][ j ] = distance ; } } } } } } return ans ; } //Driver Code Starts static void Main () { int [ ] grid = { { 0 1 1 0 } { 1 1 0 0 } { 0 0 1 1 } }; List < List < int > > ans = nearest ( grid ); for ( int i = 0 ; i < ans . Count ; i ++ ) { for ( int j = 0 ; j < ans [ i ]. Count ; j ++ ) { Console . Write ( ans [ i ][ j ] + ' ' ); } Console . WriteLine (); } } } //Driver Code Ends
JavaScript function nearest ( grid ) { let n = grid . length ; let m = grid [ 0 ]. length ; let ans = new Array ( n ); for ( let i = 0 ; i < n ; i ++ ) { ans [ i ] = new Array ( m ). fill ( Infinity ); } // visit each cell of the grid for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < m ; j ++ ) { // if the cell has 1 // then the distance is 0 if ( grid [ i ][ j ] === 1 ) { ans [ i ][ j ] = 0 ; continue ; } // iterate over all the cells // and find the distance of the nearest 1 for ( let k = 0 ; k < n ; k ++ ) { for ( let l = 0 ; l < m ; l ++ ) { if ( grid [ k ][ l ] === 1 ) { ans [ i ][ j ] = Math . min ( ans [ i ][ j ] Math . abs ( i - k ) + Math . abs ( j - l )); } } } } } return ans ; } // Driver Code //Driver Code Starts let grid = [ [ 0 1 1 0 ] [ 1 1 0 0 ] [ 0 0 1 1 ] ]; let ans = nearest ( grid ); for ( let i = 0 ; i < ans . length ; i ++ ) { console . log ( ans [ i ]. join ( ' ' )); } //Driver Code Ends
Çıkış
1 0 0 1 0 0 1 1 1 1 0 0
[Beklenen Yaklaşım] - Önce Genişlik Aramasını Kullanma - O(n * m) Zaman ve O(n * m) Uzay
C++Sorun, çok kaynaklı bir BFS yaklaşımı kullanılarak verimli bir şekilde çözülebilir. Izgaradaki her hücre, bitişik hücreleri birbirine bağlayan kenarları olan bir düğüm olarak ele alınır (yukarı, sol, sağ). Her 0 hücre için ayrı bir arama yapmak yerine, başlangıçta 1 içeren tüm hücreleri sıraya alıyoruz ve bu birden fazla kaynaktan aynı anda tek bir BFS gerçekleştiriyoruz. BFS katman katman genişledikçe, ziyaret edilmeyen her 0 hücrenin mesafesini, üst hücrenin mesafesinden bir fazla olacak şekilde güncelliyoruz. Bu, her hücrenin en yakın 1'e minimum mesafeyi optimum ve verimli bir şekilde almasını garanti eder.
//Driver Code Starts #include #include #include #include using namespace std ; //Driver Code Ends vector < vector < int >> nearest ( vector < vector < int >> & grid ) { int n = grid . size (); int m = grid [ 0 ]. size (); vector < vector < int >> ans ( n vector < int > ( m INT_MAX )); // to store the indices of the cells having 1 queue < pair < int int >> q ; // visit each cell of the grid for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if the cell has 1 // then the distance is 0 if ( grid [ i ][ j ] == 1 ) { ans [ i ][ j ] = 0 ; q . push ({ i j }); } } } // iterate over all the cells // and find the distance of the nearest 1 while ( ! q . empty ()) { int len = q . size (); for ( int i = 0 ; i < len ; i ++ ) { int x = q . front (). first ; int y = q . front (). second ; q . pop (); // check all the four directions vector < vector < int >> directions = {{ 0 1 } { 0 -1 } { 1 0 } { -1 0 }}; for ( int j = 0 ; j < directions . size (); j ++ ) { int dx = directions [ j ][ 0 ]; int dy = directions [ j ][ 1 ]; // if the cell is within the grid // and the distance is not calculated yet if ( x + dx >= 0 && x + dx < n && y + dy >= 0 && y + dy < m && ans [ x + dx ][ y + dy ] == INT_MAX ) { ans [ x + dx ][ y + dy ] = ans [ x ][ y ] + 1 ; q . push ({ x + dx y + dy }); } } } } return ans ; } //Driver Code Starts int main () { vector < vector < int >> grid = {{ 0 1 1 0 } { 1 1 0 0 } { 0 0 1 1 }}; vector < vector < int >> ans = nearest ( grid ); for ( int i = 0 ; i < ans . size (); i ++ ) { for ( int j = 0 ; j < ans [ i ]. size (); j ++ ) { cout < < ans [ i ][ j ] < < ' ' ; } cout < < endl ; } return 0 ; } //Driver Code Ends
Java //Driver Code Starts import java.util.ArrayList ; import java.util.Queue ; import java.util.LinkedList ; import java.util.Arrays ; class GfG { //Driver Code Ends static ArrayList < ArrayList < Integer >> nearest ( int [][] grid ) { int n = grid . length ; int m = grid [ 0 ] . length ; int [][] ans = new int [ n ][ m ] ; for ( int i = 0 ; i < n ; i ++ ) { Arrays . fill ( ans [ i ] Integer . MAX_VALUE ); } // to store the indices of the cells having 1 Queue < int []> q = new LinkedList <> (); // visit each cell of the grid for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if the cell has 1 // then the distance is 0 if ( grid [ i ][ j ] == 1 ) { ans [ i ][ j ] = 0 ; q . add ( new int [] { i j }); } } } // iterate over all the cells // and find the distance of the nearest 1 while ( ! q . isEmpty ()) { int len = q . size (); for ( int i = 0 ; i < len ; i ++ ) { int [] front = q . poll (); int x = front [ 0 ] ; int y = front [ 1 ] ; // check all the four directions int [][] directions = {{ 0 1 } { 0 - 1 } { 1 0 } { - 1 0 }}; for ( int j = 0 ; j < directions . length ; j ++ ) { int dx = directions [ j ][ 0 ] ; int dy = directions [ j ][ 1 ] ; // if the cell is within the grid // and the distance is not calculated yet if ( x + dx >= 0 && x + dx < n && y + dy >= 0 && y + dy < m && ans [ x + dx ][ y + dy ] == Integer . MAX_VALUE ) { ans [ x + dx ][ y + dy ] = ans [ x ][ y ] + 1 ; q . add ( new int [] { x + dx y + dy }); } } } } ArrayList < ArrayList < Integer >> result = new ArrayList <> (); for ( int i = 0 ; i < n ; i ++ ) { ArrayList < Integer > row = new ArrayList <> (); for ( int j = 0 ; j < m ; j ++ ) { row . add ( ans [ i ][ j ] ); } result . add ( row ); } return result ; } //Driver Code Starts public static void main ( String [] args ) { int [][] grid = {{ 0 1 1 0 } { 1 1 0 0 } { 0 0 1 1 }}; ArrayList < ArrayList < Integer >> ans = nearest ( grid ); for ( ArrayList < Integer > row : ans ) { for ( int val : row ) { System . out . print ( val + ' ' ); } System . out . println (); } } } //Driver Code Ends
Python #Driver Code Starts from collections import deque import sys #Driver Code Ends def nearest ( grid ): n = len ( grid ) m = len ( grid [ 0 ]) ans = [[ sys . maxsize for _ in range ( m )] for _ in range ( n )] # to store the indices of the cells having 1 q = deque () # visit each cell of the grid for i in range ( n ): for j in range ( m ): # if the cell has 1 # then the distance is 0 if grid [ i ][ j ] == 1 : ans [ i ][ j ] = 0 q . append (( i j )) # iterate over all the cells # and find the distance of the nearest 1 while q : len_q = len ( q ) for _ in range ( len_q ): x y = q . popleft () # check all the four directions directions = [( 0 1 ) ( 0 - 1 ) ( 1 0 ) ( - 1 0 )] for dx dy in directions : # if the cell is within the grid # and the distance is not calculated yet if 0 <= x + dx < n and 0 <= y + dy < m and ans [ x + dx ][ y + dy ] == sys . maxsize : ans [ x + dx ][ y + dy ] = ans [ x ][ y ] + 1 q . append (( x + dx y + dy )) return ans #Driver Code Starts if __name__ == '__main__' : grid = [[ 0 1 1 0 ] [ 1 1 0 0 ] [ 0 0 1 1 ]] ans = nearest ( grid ) for row in ans : print ( ' ' . join ( map ( str row ))) #Driver Code Ends
C# //Driver Code Starts using System ; using System.Collections.Generic ; class GFG { //Driver Code Ends static List < List < int >> nearest ( int [] grid ) { int n = grid . GetLength ( 0 ); int m = grid . GetLength ( 1 ); int [] ans = new int [ n m ]; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { ans [ i j ] = int . MaxValue ; } } // to store the indices of the cells having 1 Queue < Tuple < int int >> q = new Queue < Tuple < int int >> (); // visit each cell of the grid for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if the cell has 1 // then the distance is 0 if ( grid [ i j ] == 1 ) { ans [ i j ] = 0 ; q . Enqueue ( new Tuple < int int > ( i j )); } } } // iterate over all the cells // and find the distance of the nearest 1 while ( q . Count > 0 ) { int len = q . Count ; for ( int i = 0 ; i < len ; i ++ ) { var node = q . Dequeue (); int x = node . Item1 ; int y = node . Item2 ; // check all the four directions int [] directions = new int [] { { 0 1 } { 0 - 1 } { 1 0 } { - 1 0 } }; for ( int j = 0 ; j < 4 ; j ++ ) { int dx = directions [ j 0 ]; int dy = directions [ j 1 ]; // if the cell is within the grid // and the distance is not calculated yet if ( x + dx >= 0 && x + dx < n && y + dy >= 0 && y + dy < m && ans [ x + dx y + dy ] == int . MaxValue ) { ans [ x + dx y + dy ] = ans [ x y ] + 1 ; q . Enqueue ( new Tuple < int int > ( x + dx y + dy )); } } } } // Convert 2D array to List > before returning
List < List < int >> result = new List < List < int >> (); for ( int i = 0 ; i < n ; i ++ ) { List < int > row = new List < int > (); for ( int j = 0 ; j < m ; j ++ ) { row . Add ( ans [ i j ]); } result . Add ( row ); } return result ; } //Driver Code Starts static void Main () { int [] grid = new int [] { { 0 1 1 0 } { 1 1 0 0 } { 0 0 1 1 } }; List < List < int >> ans = nearest ( grid ); for ( int i = 0 ; i < ans . Count ; i ++ ) { for ( int j = 0 ; j < ans [ i ]. Count ; j ++ ) { Console . Write ( ans [ i ][ j ] + ' ' ); } Console . WriteLine (); } } } //Driver Code Ends
JavaScript //Driver Code Starts const Denque = require ( 'denque' ); //Driver Code Ends function nearest ( grid ) { let n = grid . length ; let m = grid [ 0 ]. length ; // Initialize answer matrix with Infinity let ans = []; for ( let i = 0 ; i < n ; i ++ ) { ans . push ( new Array ( m ). fill ( Infinity )); } // to store the indices of the cells having 1 let q = new Denque (); // visit each cell of the grid for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < m ; j ++ ) { // if the cell has 1 // then the distance is 0 if ( grid [ i ][ j ] === 1 ) { ans [ i ][ j ] = 0 ; q . push ([ i j ]); } } } // iterate over all the cells // and find the distance of the nearest 1 while ( ! q . isEmpty ()) { let [ x y ] = q . shift (); // check all the four directions let directions = [ [ 0 1 ] [ 0 - 1 ] [ 1 0 ] [ - 1 0 ] ]; for ( let dir of directions ) { let dx = dir [ 0 ]; let dy = dir [ 1 ]; // if the cell is within the grid // and the distance is not calculated yet if ( x + dx >= 0 && x + dx < n && y + dy >= 0 && y + dy < m && ans [ x + dx ][ y + dy ] === Infinity ) { ans [ x + dx ][ y + dy ] = ans [ x ][ y ] + 1 ; q . push ([ x + dx y + dy ]); } } } return ans ; } //Driver Code Starts // Driver Code let grid = [ [ 0 1 1 0 ] [ 1 1 0 0 ] [ 0 0 1 1 ] ]; let ans = nearest ( grid ); for ( let i = 0 ; i < ans . length ; i ++ ) { console . log ( ans [ i ]. join ( ' ' )); } //Driver Code Ends
Çıkış
1 0 0 1 0 0 1 1 1 1 0 0Test Oluştur
