이진 행렬에서 1을 갖는 가장 가까운 셀의 거리
GfG Practice에서 사용해 보세요. 
산출
산출
바이너리가 주어지면 그리드[][] . 가장 가까운 거리를 찾아보세요. 1 각 셀의 그리드에
거리는 다음과 같이 계산됩니다. |나 1 - 나 2 | + |j 1 -j 2 | 내가 어디 1 j 1 는 현재 셀의 행 번호와 열 번호이고 i는 2 j 2 값이 1인 가장 가까운 셀의 행 번호와 열 번호입니다.
메모: 그리드에는 값이 1인 셀이 하나 이상 있어야 합니다.
예:
입력: 그리드[][] = [[0 1 1 0]
[1 1 0 0]
[0 0 1 1]]
산출: [[1 0 0 1]
[0 0 1 1]
[1 1 0 0]]
설명:
셀(0 1)은 셀(0 0)에서 가장 가까운 1을 가집니다 - 거리 = |0-0| + |0-1| = 1
셀(0 2)은 셀(0 3)에서 가장 가까운 1을 가집니다 - 거리 = |0-0| + |3-2| = 1
셀 (1 0)은 셀 (0 0)에서 가장 가까운 1을 가집니다 - 거리 = |1-0| + |0-0| = 1
셀 (1 1)은 셀 (1 2)에서 가장 가까운 1을 가집니다 - 거리 = |1-1| + |1-2| = 1
셀 (2 2)는 셀 (2 1)에서 가장 가까운 1을 가집니다 - 거리 = |2-2| + |2-1| = 1
셀 (2 3)은 셀 (1 3)에서 가장 가까운 1을 가집니다 - 거리 = |2-1| + |3-3| = 1
나머지는 모두 1을 갖는 셀이므로 1을 갖는 가장 가까운 셀과의 거리는 0입니다.입력: 그리드[][] = [[1 0 1]
[1 1 0]
[1 0 0]]
산출: [[0 1 0]
[0 0 1]
[0 1 2]]
설명:
셀(0 0)은 셀(0 1)에서 가장 가까운 1을 가집니다. - 거리 = |0-0| + |0-1| = 1
셀(0 2)은 셀(0 1)에서 가장 가까운 1을 가집니다. - 거리 = |0-0| + |2-1| = 1
셀 (1 0)은 셀 (0 1)에서 가장 가까운 1을 가집니다 - 거리 = |1-0| + |0-1| = 2
셀 (1 1)은 셀 (1 2)에서 가장 가까운 1을 가집니다 - 거리 = |1-1| + |1-2| = 1
셀(2 0)은 셀(2 1)에서 가장 가까운 1을 가집니다. - 거리 = |2-2| + |2-1| = 1
셀 (2 2)는 셀 (2 1)에서 가장 가까운 1을 가집니다 - 거리 = |2-2| + |2-1| = 1
나머지는 모두 1을 갖는 셀이므로 1을 갖는 가장 가까운 셀과의 거리는 0입니다.
목차
[순진한 접근 방식] - O((n*m)^2) 시간 및 O(n * m) 공간
C++아이디어는 전체 그리드를 탐색하고 각 셀의 거리를 가장 가까운 1까지 계산하는 것입니다.
- 셀에 1이 포함되어 있으면 해당 거리는 0입니다.
- 셀에 0이 포함되어 있으면 전체 그리드를 탐색하여 1이 포함된 가장 가까운 셀을 찾습니다.
- 각 0 셀에 대해 1인 모든 셀까지의 맨해튼 거리를 계산하고 최소 거리를 취합니다.
결과 행렬의 해당 셀에 이 최소 거리를 저장합니다. 그리드의 모든 셀에 대해 반복합니다.
//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
산출
1 0 0 1 0 0 1 1 1 1 0 0
[예상 접근 방식] - 너비 우선 탐색 사용 - O(n * m) 시간과 O(n * m) 공간
C++다중 소스 BFS 접근 방식을 사용하면 문제를 효율적으로 해결할 수 있습니다. 그리드의 각 셀은 인접한 셀을 연결하는 가장자리가 있는 노드로 처리됩니다(위 아래 왼쪽 오른쪽). 모든 0 셀에 대해 별도의 검색을 실행하는 대신 시작 시 1을 포함하는 모든 셀을 대기열에 추가하고 이러한 여러 소스에서 동시에 단일 BFS를 수행합니다. BFS가 레이어별로 확장됨에 따라 방문하지 않은 각 0 셀의 거리를 상위 셀의 거리보다 1 더 크게 업데이트합니다. 이는 모든 셀이 최적의 효율적인 방식으로 가장 가까운 1까지의 최소 거리를 수신하도록 보장합니다.
//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
산출
1 0 0 1 0 0 1 1 1 1 0 0퀴즈 만들기
