Check If Cells Numbered 1 to K In A Grid Can Be Connected After The Removal Of At most One Blocked Cell

Introduction

Grid questions are other ways to represent questions based on Graph Traversals and related algorithms.

Questions on Grid and its Traversal are increasingly becoming very common in programming interviews. Therefore it is necessary to master questions based on Grid Traversals or Graph Traversals and their applications to ace technical interviews of big companies.

Problem Statement

Given a grid A of size N*M with K cells represented by values in the range [1, K], some blocked cells designated by -1, and the other unblocked cells denoted by 0, the challenge is to determine if it is possible to link those K cells, either directly or indirectly, by unblocking at most one cell. It's only possible to navigate between the neighbouring horizontal and vertical cells.

Example:

Input

Assume we have the following grid as input:

Grid = {
	 	{0, 5, 6, 0}, 
     		{3, -1, -1, 4}, 
     		{-1, 2, 1, -1}, 
     		{-1, -1, -1, -1}
       }
K = 6


Output

YES


Explanation:

All of the K cells would be linked if cell (2, 2), (2, 3), (3, 1), or (3, 4) was unblocked.

Approach

  • We simply need to traverse the whole grid and check for connected parts.
     
  • From cells that have values between 1 and K, perform BFS and label each cell with the component to which it belongs. 
     
  • Check for any blocked cells that have neighbouring cells from different components. 
     
  • If any are present, they can be connected by unblocking that cell. It is not feasible otherwise.

Code

#include <bits/stdc++.h>
using namespace std;

void check(int k, vector<vector<int> > grid)
{
    int n=grid.size();
    int m=grid[0].size();
	int cells[k][2];
	bool visited[n][m];//boolean grid for checking visited 
	int count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {

			if (grid[i][j] != 0
				&& grid[i][j] != -1) {

				cells[count][0] = i;
				cells[count][1] = j;
				count++;
			}
			//marking not visited
			visited[i][j] = false;
		}
	}

	//4 directions ajdacent
	int dx[] = { 0, 0, 1, -1 };
	int dy[] = { 1, -1, 0, 0 };

	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];
        //checking if already visited
		if (visited[x][y])
			continue;
		component++;
		queue<pair<int,int>> cells;
		cells.push(make_pair(x, y));
		visited[x][y] = true;

		while (!cells.empty()) {

			pair<int,int> z = cells.front();
			cells.pop();
			grid[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]
					|| grid[new_x][new_y] == -1)
					continue;
                //pushing to the queue.
				cells.push(make_pair(new_x, new_y));
				//Marking Visited
				visited[new_x][new_y] = true;
			}
		}
	}

	int maximum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
            //checking for blocked
			if (grid[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 (grid[xx][yy] <= 0)
						continue;
					set.insert(grid[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;
	vector<vector<int> > grid
		= { { 0, 5, 6, 0 },
			{ 3, -1, -1, 4 },
			{ -1, 2, 1, -1 },
			{ -1, -1, -1, -1 } };

	check(k, grid);
	return 0;
}


Output

YES

Complexity Analysis

Time Complexity: O(N*M)

Where our grid is of size N x M. Since we need to traverse each cell of the grid because for every cell we need to check if it is already visited or not, and if not visited we push its neighbours into the queue. After working on the cells numbered from 1 to k we again run a loop to traverse over all of the cells to check If the cell is blocked and if it can connect two different components or not.

Space Complexity: O(N*M)

Because we created an extra grid of N x M to keep track of visited cells.

Frequently Asked Questions

  1. What is a BFS?
    The Breadth-First Search (BFS) technique is used to traverse or search data structures such as trees and graphs. Before going on to the nodes at the next depth level, it investigates all of the nodes at the current depth.
     
  2. How can we Implement BFS?
    BFS can be implemented using a queue.
     
  3. What is the complexity of  BFS if our graph is in the form of Adjacency List rather than matrix?
    The time complexity of BFS in the case of adjacency list representation of a graph is O(V + E) where V is the number of vertexes and E is the number of edges in the graph.

Key Takeaways

The BFS algorithm (breath first search) is a well-known graph/tree traversal technique. The essential idea is that each node visits each of its children before moving on to their children's children. The data structure utilised to achieve BFS is a queue. It's commonly employed in issues requiring the determination of an optimal value, such as determining the shortest path in an unweighted graph.

You can learn more about queue and its applications by visiting here.

To practise more BFS related questions click BFS Interview Problems.

If you wish to practice more questions based on graph traversal and algorithms you can visit Top Graph Problems.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think