Проверьте, можно ли соединить ячейки с номерами от 1 до K в сетке после удаления хотя бы одной заблокированной ячейки
Опубликовано: 7 Января, 2022
Для сетки 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 approachimport 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 approachfrom collections import deque as queuedef 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])РЕКОМЕНДУЕМЫЕ СТАТЬИ |