Проверьте, можно ли соединить ячейки с номерами от 1 до K в сетке после удаления хотя бы одной заблокированной ячейки
Для сетки A размера N * M, состоящей из K ячеек, обозначенных значениями в диапазоне [1, K] , некоторых заблокированных ячеек, обозначенных -1, и оставшихся незаблокированных ячеек, обозначенных 0 , задача состоит в том, чтобы проверить, возможно ли соединение эти К-клетки, прямо или косвенно, разблокировав хотя бы одну клетку. Возможен переход только в соседние горизонтальные и соседние вертикальные ячейки.
Примеры
Вход: А = {{0, 5, 6, 0}, {3, -1, -1, 4}, {-1, 2, 1, -1}, {-1, -1, -1, -1}}, К = 6 Выход: Да Объяснение: Разблокирование ячейки (2, 2) или (2, 3) или (3, 1) или (3, 4) сделали бы все K ячеек связанными. Вход: А = {{-1, -1, 3, -1}, {1, 0, -1, -1}, {-1, -1, -1, 0}, {-1, 0, 2, -1}}, К = 3 Выход: Нет Объяснение: Необходимо разблокировать как минимум две ячейки.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: выполните BFS из ячеек, пронумерованных от 1 до K, и пометьте каждую ячейку компонентом, которому она принадлежит. Проверьте, есть ли какие-либо заблокированные ячейки, в которых соседние ячейки принадлежат разным компонентам. Если они есть, то можно подключиться, разблокировав эту ячейку. В противном случае это невозможно.
Пример:
After performing BFS and labeling the cells by their no of components, the array appears as follows:
A={{1, 1, 1, 1}, {1, -1, -1, 1}, {-1, 2, 2, -1}, {-1, -1, -1, -1}}
The number of different label around the cell (2, 2) is 2.
Hence, unblocking it will connect the K cells.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; #define pairs pair<int, int> void check( int k, vector<vector< int > > a, int n, int m) { int cells[k][2]; bool visited[n][m]; int count = 0; for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (a[i][j] != 0 && a[i][j] != -1) { cells[count][0] = i; cells[count][1] = j; count++; } visited[i][j] = false ; } } // Arrays to make grid traversals easier int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; // Store number of components int component = 0; // Perform BFS and maark every cell // by the component in which it belongs for ( int i = 0; i < k; i++) { int x = cells[i][0], y = cells[i][1]; if (visited[x][y]) continue ; component++; queue<pairs> cells; cells.push(make_pair(x, y)); visited[x][y] = true ; while (!cells.empty()) { pairs z = cells.front(); cells.pop(); a[z.first][z.second] = component; for ( int j = 0; j < 4; j++) { int new_x = z.first + dx[j]; int new_y = z.second + dy[j]; if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m) continue ; if (visited[new_x][new_y] || a[new_x][new_y] == -1) continue ; cells.push(make_pair(new_x, new_y)); visited[new_x][new_y] = true ; } } } int maximum = 0; for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (a[i][j] == -1) { unordered_set< int > set; for ( int kk = 0; kk < 4; kk++) { int xx = i + dx[kk]; int yy = j + dy[kk]; if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue ; // if the cell doesn"t // belong to any component if (a[xx][yy] <= 0) continue ; set.insert(a[xx][yy]); } int s = set.size(); maximum = max(s, maximum); } } } if (maximum == component) { cout << "Yes
" ; } else { cout << "No
" ; } } int main() { int k = 6; int n = 4, m = 4; vector<vector< int > > a = { { 0, 5, 6, 0 }, { 3, -1, -1, 4 }, { -1, 2, 1, -1 }, { -1, -1, -1, -1 } }; check(k, a, n, m); return 0; } |
Java
// Java implementation of the above approach import java.util.*; class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } static void check( int k, int [][]a, int n, int m) { int [][]cell = new int [k][ 2 ]; boolean [][]visited = new boolean [n][m]; int count = 0 ; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { if (a[i][j] != 0 && a[i][j] != - 1 ) { cell[count][ 0 ] = i; cell[count][ 1 ] = j; count++; } visited[i][j] = false ; } } // Arrays to make grid traversals easier int dx[] = { 0 , 0 , 1 , - 1 }; int dy[] = { 1 , - 1 , 0 , 0 }; // Store number of components int component = 0 ; // Perform BFS and maark every cell // by the component in which it belongs for ( int i = 0 ; i < k; i++) { int x = cell[i][ 0 ], y = cell[i][ 1 ]; if (visited[x][y]) continue ; component++; Queue<pair> cells = new LinkedList<>(); cells.add( new pair(x, y)); visited[x][y] = true ; while (!cells.isEmpty()) { pair z = cells.peek(); cells.remove(); a[z.first][z.second] = component; for ( int j = 0 ; j < 4 ; j++) { int new_x = z.first + dx[j]; int new_y = z.second + dy[j]; if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m) continue ; if (visited[new_x][new_y] || a[new_x][new_y] == - 1 ) continue ; cells.add( new pair(new_x, new_y)); visited[new_x][new_y] = true ; } } } int maximum = 0 ; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { if (a[i][j] == - 1 ) { HashSet<Integer> set = new HashSet<Integer>(); for ( int kk = 0 ; kk < 4 ; kk++) { int xx = i + dx[kk]; int yy = j + dy[kk]; if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue ; // if the cell doesn"t // belong to any component if (a[xx][yy] <= 0 ) continue ; set.add(a[xx][yy]); } int s = set.size(); maximum = Math.max(s, maximum); } } } if (maximum == component) { System.out.print( "Yes
" ); } else { System.out.print( "No
" ); } } public static void main(String[] args) { int k = 6 ; int n = 4 , m = 4 ; int [][]a = { { 0 , 5 , 6 , 0 }, { 3 , - 1 , - 1 , 4 }, { - 1 , 2 , 1 , - 1 }, { - 1 , - 1 , - 1 , - 1 } }; check(k, a, n, m); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the above approach from collections import deque as queue def check(k, a, n, m): cells = [[ 0 for i in range ( 2 )] for i in range (k)] visited = [[ 0 for i in range (m)] for i in range (n)] count = 0 for i in range (n): for j in range (m): if (a[i][j] ! = 0 and a[i][j] ! = - 1 ): cells[count][ 0 ] = i cells[count][ 1 ] = j count + = 1 visited[i][j] = False # Arrays to make grid traversals easier dx = [ 0 , 0 , 1 , - 1 ] dy = [ 1 , - 1 , 0 , 0 ] # Store number of components component = 0 # Perform BFS and maark every cell # by the component in which it belongs for i in range (k): x = cells[i][ 0 ] y = cells[i][ 1 ] if (visited[x][y]): continue component + = 1 cell = queue() cell.append([x, y]) visited[x][y] = True while ( len (cell) > 0 ): z = cell.popleft() a[z[ 0 ]][z[ 1 ]] = component for j in range ( 4 ): new_x = z[ 0 ] + dx[j] new_y = z[ 1 ] + dy[j] if (new_x < 0 or new_x > = n or new_y < 0 or new_y > = m): continue if (visited[new_x][new_y] or a[new_x][new_y] = = - 1 ): continue cell.append([new_x, new_y]) РЕКОМЕНДУЕМЫЕ СТАТЬИ |