How to create a graph for this?

general
, , ,
1

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?

2

@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
3

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[0]-'a', pos[1]-'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
4

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

5

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

6

@utkarsh1729 keep learning :+1: !!!