Day 34 | Solving Grids like Graphs | C++

Do you also feel same as above when solving some problems. It will be marked as graphs or dfs-and-similar but there won't a graph given. Or you will be trying to solve a 2-D array problem and suddenly see word dfs or bfs in the tutorial?

Do you want to learn why and how competitive programmers use graphs to solve grid (2-D array) problems?

Let's get started with then

Consider a 3x3 grid, in which you can move left, right, up and down. Like Figure A below.

Now If I draw, arrows for the possible movement, graph will become something like this -

If you add some space between blocks, you will get something like this

Each node can be considered a node and you can assume edge existing towards cell you can reach. Thus we can perceive this grid as graph.

Why would you want to perceive grid as graph?

This solves many problems which are already solved regularly in graphs -

For example

1. Connected Components [Island and Water problem in Interviews]

2. Bridges [Very Common OA problem in 2020-21, cannot comment about current time]

3. Shortest Path [Germs reaching target problem, Path to escape problems]

4. and so many other problems

How to make a graph in grid?

Do you remember what you need to make a graph?

1. Vertices

2. Edges

In grid, each cell is a vertex. And you know where you can go from each cell, so you also have edges. You do not need to store it as proper graph.

Let's say you have a grid, vector<vector<int>> grid;

You can run a dfs on it like this

vector<vector<int>> grid;
vector<vector<bool>> vis;

void valid(int i, int j){
    if(i >= 0 && j >= 0 && i < grid.size() && j < grid.back().size()
        && !vis[i][j])
        return true;
    // By default
    return false;
} 

void dfs(int i, int j){
    if(!valid(i,j))
        return;
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    for(int dir = 0; dir < 4; dir++)
        dfs(i + dx[dir], j + dy[dir]);
}

Let's solve Counting Rooms

Problem is quite simple, similar to what we did yesterday but considering grid as graph.

We have to count the number of connected components.

You can do the same thing in grid like this

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

vector<string> arr;
vector<vector<int>> vis;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

bool valid(int i, int j){
    if(i >= 0 && j >= 0 && i < arr.size() && j < arr.back().size() 
        && arr[i][j] == '.' && vis[i][j] == 0)
        return true;
    return false;
}

void dfs(int x, int y){
    if(!valid(x,y))return;
    vis[x][y] = 1;
    for(int i = 0; i < 4; i++)
         dfs(x + dx[i], y + dy[i]);
}

int main(){
    int n,m;
    cin >> n >> m;
    arr = vector<string> (n);
    for(auto &i: arr)
        cin >> i;
    vis = vector<vector<int>> (n, vector<int> (m,0));
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!valid(i,j))continue;
            ans++;
            dfs(i,j);
        }
    }
    cout << ans;
    return 0;
} 

Please like and share my posts if they are helpful.