 # How to create a graph for this?

Here is a problem that I found on SPOJ which can be solved using BFS:-

Now, though I know how to apply BFS but here I am stuck with the problem of creating a graph to which I can apply the BFS. How can I create an adjacency list for this problem?

@utkarsh1729 there is no need to construct a graph for this just a simple BFS grid traversal would suffice your need. Solve SPOJ_NATALIAG before this to have an idea of what is involved in the above problem.

1 Like

You don’t need to explicitly create the graph. From each node you know the possible directions, so just store them in a vector

Implementation
``````#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
pair<int, int> operator+(const pair<int,int> &x, const pair<int,int> &y){
return mp(x.first + y.first, x.second + y.second);
}
void solve(){
string pos1;
string pos2;
cin>>pos1>>pos2;
const auto find=[&](const string &pos){
return mp(pos-'a', pos-'1');
};
vector<pair<int,int>> dirs;
for(int i=0;i<4;i++){
dirs.pb(mp(1 * ((i&1) ? 1 : -1), 2*((i&2) ? 1 : -1)));
dirs.pb(mp(2 * ((i&1) ? 1 : -1), 1*((i&2) ? 1 : -1)));
}
const auto start=find(pos1);
const auto end=find(pos2);
vector<vector<int>> dist(8, vector<int>(8, -1));
const auto valid = [&](const pair<int,int> &pos){
if(pos.first<0 || pos.first>=8){
return false;
}
if(pos.second<0 || pos.second>=8){
return false;
}
if(dist[pos.first][pos.second]!=-1){
return false;
}
return true;
};
queue<pair<int,int>> tochk;
tochk.push(start);
dist[start.first][start.second]=0;
while(!tochk.empty()){
const auto curr=tochk.front();
tochk.pop();
for(const auto &dir : dirs){
const auto now=curr+dir;
if(valid(now)){
dist[now.first][now.second]=dist[curr.first][curr.second]+1;
tochk.push(now);
}
}
}
cout<<dist[end.first][end.second]<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
}
``````
2 Likes

Thanks @everule1. Though I could not come up with a solution as short as yours, it did help me.

Thanks @ankit_ap99 for referring that problem. I learnt a new technique because of this.

@utkarsh1729 keep learning !!!