Проверьте, можно ли соединить ячейки с номерами от 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 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])