바이너리가 주어지면 그리드[][] . 가장 가까운 거리를 찾아보세요. 1 각 셀의 그리드에
거리는 다음과 같이 계산됩니다. |나 1 - 나 2 | + |j 1 -j 2 | 내가 어디1j1 는 현재 셀의 행 번호와 열 번호이고 i는2j2 값이 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까지 계산하는 것입니다.
np 표준
- 셀에 1이 포함되어 있으면 해당 거리는 0입니다.
- 셀에 0이 포함되어 있으면 전체 그리드를 탐색하여 1이 포함된 가장 가까운 셀을 찾습니다.
- 각 0 셀에 대해 1인 모든 셀까지의 맨해튼 거리를 계산하고 최소 거리를 취합니다.
결과 행렬의 해당 셀에 이 최소 거리를 저장합니다. 그리드의 모든 셀에 대해 반복합니다.
//Driver Code Starts #include
//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
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
//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
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
//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 = {{0110} {1100} {0011}}; 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
#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 = [[0110] [1100] [0011]] ans = nearest(grid) for row in ans: print(' '.join(map(str row))) #Driver Code Ends
//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
//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퀴즈 만들기