Check if cells numbered 1 to K in a grid can be connected after removal of atmost one blocked cell

0 0 16 minutes read

Given a grid A of size N*M consisting of K cells denoted by values in range [1, K], some blocked cells denoted by -1 and remaining unblocked cells denoted by 0, the task is to check if it is possible to connect those K cells, directly or indirectly, by unblocking atmost one cell. It is possible to move only to the adjacent horizontal and adjacent vertical cells.

Examples

Input:
A = {{0, 5, 6, 0}, 
     {3, -1, -1, 4}, 
     {-1, 2, 1, -1}, 
     {-1, -1, -1, -1}},
K = 6
Output: Yes
Explanation: 
Unblocking cell (2, 2) or (2, 3) or (3, 1) or
(3, 4) would make all the K cells connected.
Input:
A = {{-1, -1, 3, -1}, 
     {1, 0, -1, -1}, 
     {-1, -1, -1, 0}, 
     {-1, 0, 2, -1}},
K = 3
Output: No
Explanation:
Atleast two cells need to be unblocked.

Approach: Perform BFS from the cells numbered 1 to K and mark every cell by the component to which it belongs. Check if there is any blocked cell having adjacent cells belonging to different components. If there exists any, then it is possible to connect by unblocking that cell. Otherwise, it is not possible.

Example:

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 mark 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\n";
    }
    else {
        cout << "No\n";
    }
}
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.*;
 
public 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 mark 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\n");
    }
    else {
        System.out.print("No\n");
    }
}
 
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 mark 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])
                visited[new_x][new_y] = True
 
    maximum = 0
    for i in range(n):
        for j in range(m):
 
            if (a[i][j] == -1):
                se = dict()
                for kk in range(4):
 
                    xx = i + dx[kk]
                    yy = j + dy[kk]
                    if (xx < 0 or xx >= n
                        or yy < 0 or yy >= m):
                        continue
 
                    # if the cell doesn't
                    # belong to any component
                    if (a[xx][yy] <= 0):
                        continue
                    se[a[xx][yy]] = 1
 
                s = len(se)
                maximum = max(s, maximum)
 
    if (maximum == component):
        print("Yes\n")
 
    else:
        print("No\n")
 
# Driver code
if __name__ == '__main__':
    k = 6
    n = 4
    m = 4
    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 mohit kumar 29

C#

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GFG{
    class pair
    { 
        public 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];
    bool [,]visited = new bool[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 mark 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++;
        List<pair> cells = new List<pair>();
        cells.Add(new pair(x, y));
        visited[x, y] = true;
   
        while (cells.Count != 0) {
   
            pair z = cells[0];
            cells.RemoveAt(0);
            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<int> set = new HashSet<int>();
                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.Count;
                maximum = Math.Max(s, maximum);
            }
        }
    }
   
    if (maximum == component) {
        Console.Write("Yes\n");
    }
    else {
        Console.Write("No\n");
    }
}
  
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

Javascript

<script>
 
// Javascript implementation of the above approach
function check(k, a, n, m)
{
    var cells = Array.from(
        Array(k), () => Array(2).fill(0));
    var visited = Array.from(
        Array(n), () => Array(m).fill(0));
    var count = 0;
    for(var i = 0; i < n; i++)
    {
        for(var 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
    var dx = [ 0, 0, 1, -1 ];
    var dy = [ 1, -1, 0, 0 ];
 
    // Store number of components
    var component = 0;
 
    // Perform BFS and mark every cell
    // by the component in which it belongs
    for(var i = 0; i < k; i++)
    {
        var x = cells[i][0], y = cells[i][1];
 
        if (visited[x][y])
            continue;
             
        component++;
        var cell = [];
        cell.push([x, y]);
        visited[x][y] = true;
 
        while (cell.length != 0)
        {
            var z = cell[0];
            cell.shift();
            a[z[0]][z[1]] = component;
 
            for(var j = 0; j < 4; j++) 
            {
                var new_x = z[0] + dx[j];
                var new_y = z[1] + 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;
 
                cell.push([new_x, new_y]);
                visited[new_x][new_y] = true;
            }
        }
    }
 
    var maximum = 0;
    for(var i = 0; i < n; i++) 
    {
        for(var j = 0; j < m; j++) 
        {
            if (a[i][j] == -1) 
            {
                var set = new Set();
                for(var kk = 0; kk < 4; kk++)
                {
                    var xx = i + dx[kk];
                    var 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]);
                }
                var s = set.size;
                maximum = Math.max(s, maximum);
            }
        }
    }
    if (maximum == component)
    {
        document.write("Yes");
    }
    else
    {
        document.write("No");
    }
}
 
// Driver code
var k = 6;
var n = 4, m = 4;
 
var 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 itsok
 
</script>

Output

Yes

Performance Analysis:

Time Complexity: Performing BFS on the matrix takes O(N*M) time and O(N*M) time for checking every blocked cell. Hence the overall Time Complexity will be O(N * M).
Auxiliary Space Complexity: O(N * M)

Breadth-First Search in Python:

Approach:

We can use a breadth-first search to explore the grid, starting from each unblocked cell. We keep track of the number of visited cells and the number of unblocked cells and stop the search as soon as we find a connected path of length K.

Initialize a variable n with the length of the given matrix A.
Define a bfs function to check if there exists a path from a given cell (i, j) to any other cell in the matrix with the given value of K.
Inside the bfs function, initialize count to 1, since we start with a single cell.
Create a queue with the given starting cell (i, j) and add it to the visited set.
While the queue is not empty, pop the first element and explore its neighbors.
For each neighbor cell (ni, nj), check if it is within the bounds of the matrix, is not already visited, and is not a blocked cell (-1). If these conditions are met, add it to the visited set, add it to the queue, increment count by 1, and check if count equals K. If it does, return True, since we have found a path connecting the K cells.
If the queue becomes empty and count is not equal to K, return False, since there is no path connecting the K cells.
Iterate over all cells in the matrix A using two nested loops. If a cell is not blocked (-1) and there exists a path from it to the K cells using the bfs function, return True.
If no cell is found to be connected to the K cells, return False.

C++14

#include <deque>
#include <iostream>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
// Custom hash function for pair<int, int>
struct PairHash {
    template <typename T1, typename T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;
    }
};
 
// Function to check if there exists a connected component
// of size K
bool canBeConnected(vector<vector<int> >& A, int K)
{
    int n = A.size();
 
    // Helper function to perform BFS and check for
    // connected component of size K
    auto bfs = [&](int i, int j) {
        int count = 1;
        deque<pair<int, int> > queue;
        unordered_set<pair<int, int>, PairHash>
            visited; // Use custom hash function to store
                     // visited cells
        queue.push_back({ i, j });
        visited.insert({ i, j });
 
        while (!queue.empty()) {
            int i = queue.front().first;
            int j = queue.front().second;
            queue.pop_front();
 
            vector<pair<int, int> > directions{
                { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }
            };
            for (int d = 0; d < directions.size(); d++) {
                int ni = i + directions[d].first;
                int nj = j + directions[d].second;
 
                // Check if the neighbor cell is within
                // bounds, unvisited, and not an obstacle
                // (-1)
                if (ni >= 0 && ni < n && nj >= 0 && nj < n
                    && visited.find({ ni, nj })
                           == visited.end()
                    && A[ni][nj] != -1) {
                    visited.insert({ ni, nj });
                    queue.push_back({ ni, nj });
                    count++;
 
                    if (count == K) {
                        return true; // Connected component
                                     // of size K found
                    }
                }
            }
        }
 
        return false; // No connected component of size K
                      // found starting from the current
                      // cell
    };
 
    // Check each cell in the grid for a connected component
    // of size K
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j] != -1 && bfs(i, j)) {
                return true; // Connected component of size
                             // K found in the grid
            }
        }
    }
 
    return false; // No connected component of size K found
                  // in the grid
}
 
int main()
{
    vector<vector<int> > A{ { 0, 5, 6, 0 },
                            { 3, -1, -1, 4 },
                            { -1, 2, 1, -1 },
                            { -1, -1, -1, -1 } };
    int K = 6;
 
    // Check if there exists a connected component of size K
    // in the grid A
    cout << (canBeConnected(A, K) ? "Yes" : "No") << endl;
 
    A = { { -1, -1, 3, -1 },
          { 1, 0, -1, -1 },
          { -1, -1, -1, 0 },
          { -1, 0, 2, -1 } };
    K = 3;
 
    // Check if there exists a connected component of size K
    // in the grid A
    cout << (canBeConnected(A, K) ? "Yes" : "No") << endl;
 
    // This code is contributed by Shivam Tiwari
    return 0;
}

Java

// Nikunj Sonigara
 
import java.util.*;
 
public class Main {
 
    // Custom hash function for Pair
    static class Pair {
        int first, second;
 
        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
 
        @Override
        public int hashCode() {
            return first ^ second;
        }
 
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null || getClass() != obj.getClass())
                return false;
            Pair other = (Pair) obj;
            return first == other.first && second == other.second;
        }
    }
 
    // Function to check if there exists a connected component of size K
    static boolean canBeConnected(int[][] A, int K) {
        int n = A.length;
 
        // Helper function to perform BFS and check for a connected component of size K
        Queue<Pair> queue = new ArrayDeque<>();
        Set<Pair> visited = new HashSet<>(); // Use custom hash function to store visited cells
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][j] != -1 && !visited.contains(new Pair(i, j))) {
                    int count = 1;
                    queue.add(new Pair(i, j));
                    visited.add(new Pair(i, j));
 
                    while (!queue.isEmpty()) {
                        Pair cell = queue.poll();
                        int x = cell.first;
                        int y = cell.second;
 
                        int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
 
                        for (int[] dir : directions) {
                            int ni = x + dir[0];
                            int nj = y + dir[1];
 
                            // Check if the neighbor cell is within bounds, unvisited, and not an obstacle (-1)
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n && !visited.contains(new Pair(ni, nj)) && A[ni][nj] != -1) {
                                visited.add(new Pair(ni, nj));
                                queue.add(new Pair(ni, nj));
                                count++;
 
                                if (count == K) {
                                    return true; // Connected component of size K found
                                }
                            }
                        }
                    }
                }
            }
        }
 
        return false; // No connected component of size K found in the grid
    }
 
    public static void main(String[] args) {
        int[][] A1 = { { 0, 5, 6, 0 },
                       { 3, -1, -1, 4 },
                       { -1, 2, 1, -1 },
                       { -1, -1, -1, -1 } };
        int K1 = 6;
 
        // Check if there exists a connected component of size K in the grid A1
        System.out.println(canBeConnected(A1, K1) ? "Yes" : "No");
 
        int[][] A2 = { { -1, -1, 3, -1 },
                       { 1, 0, -1, -1 },
                       { -1, -1, -1, 0 },
                       { -1, 0, 2, -1 } };
        int K2 = 3;
 
        // Check if there exists a connected component of size K in the grid A2
        System.out.println(canBeConnected(A2, K2) ? "Yes" : "No");
    }
}

Python3

from collections import deque
 
def can_be_connected(A, K):
    n = len(A)
     
    def bfs(i, j):
        count = 1
        queue = deque([(i, j)])
        visited = set([(i, j)])
        while queue:
            i, j = queue.popleft()
            for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < n and (ni, nj) not in visited and A[ni][nj] != -1:
                    visited.add((ni, nj))
                    queue.append((ni, nj))
                    count += 1
                    if count == K:
                        return True
        return False
     
    for i in range(n):
        for j in range(n):
            if A[i][j] != -1 and bfs(i, j):
                return "Yes"
                 
    return "No"
 
# example usage
A = [[0, 5, 6, 0], 
     [3, -1, -1, 4], 
     [-1, 2, 1, -1], 
     [-1, -1, -1, -1]]
K = 6
print(can_be_connected(A, K)) # output: "Yes"
 
A = [[-1, -1, 3, -1], 
     [1, 0, -1, -1], 
     [-1, -1, -1, 0], 
     [-1, 0, 2, -1]]
K = 3
print(can_be_connected(A, K)) # output: "No"

C#

using System;
using System.Collections.Generic;
 
public class Program {
    public static bool CanBeConnected(int[][] A, int K) {
        int n = A.Length;
 
        Func<int, int, bool> bfs = (i, j) => {
            int count = 1;
            var queue = new Queue<Tuple<int, int>>();
            var visited = new HashSet<Tuple<int, int>>();
 
            queue.Enqueue(new Tuple<int, int>(i, j));
            visited.Add(new Tuple<int, int>(i, j));
 
            while (queue.Count > 0) {
                var current = queue.Dequeue();
                i = current.Item1;
                j = current.Item2;
 
                var directions = new List<Tuple<int, int>> {
                    Tuple.Create(0, 1),
                    Tuple.Create(1, 0),
                    Tuple.Create(0, -1),
                    Tuple.Create(-1, 0)
                };
                foreach (var dir in directions) {
                    int ni = i + dir.Item1;
                    int nj = j + dir.Item2;
 
                    var nextPos = new Tuple<int, int>(ni, nj);
                    if (ni >= 0 && ni < n && nj >= 0 && 
                        nj < n && !visited.Contains(nextPos) && 
                        A[ni][nj] != -1) {
                        visited.Add(nextPos);
                        queue.Enqueue(nextPos);
                        count++;
 
                        if (count == K) {
                            return true;
                        }
                    }
                }
            }
 
            return false;
        };
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][j] != -1 && bfs(i, j)) {
                    return true;
                }
            }
        }
 
        return false;
    }
 
    public static void Main() {
        int[][] A = {
            new[] { 0, 5, 6, 0 },
            new[] { 3, -1, -1, 4 },
            new[] { -1, 2, 1, -1 },
            new[] { -1, -1, -1, -1 }
        };
        int K = 6;
 
        Console.WriteLine(CanBeConnected(A, K) ? "Yes" : "No");
 
        A = new[] {
            new[] { -1, -1, 3, -1 },
            new[] { 1, 0, -1, -1 },
            new[] { -1, -1, -1, 0 },
            new[] { -1, 0, 2, -1 }
        };
        K = 3;
 
        Console.WriteLine(CanBeConnected(A, K) ? "Yes" : "No");
 
        //"This Code Is Contributed By Shubham Tiwari"
    }
}

Output

Yes
No

Time Complexity: O(N^2 * (N^2 + K)).
Space Complexity: O(N^2).

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!