Author: Venkatesh G Dhongadi
Tester: Venkatesh G Dhongadi
Editorialist: Venkatesh G Dhongadi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Basic 2D Graphs (Matrix representation - Wikipedia)
BFS (Breadth First Search or BFS for a Graph - GeeksforGeeks)
PROBLEM:
Problem Statement
Your hunter friend Sova has a crush on Reyna. Reyna has finally decided to go for a date with Sova ( In a hypothetical world of course ). Sova being a highly desperate fellow wants to reach her as soon as possible and keep her from waiting as Reyna is a short tempered person.
Sova has lost his recon bow that locates people and is unable to find out the path to reach Reyna. Sova needs your help in finding a path to reach his love Reyna.
Sova’s city (icebox) can be represented as a N * M grid consisting of N rows and M columns. You are given one starting point V ( Sova’s current location in icebox), one ending point S (Reyna’s location in icebox) and the rest of the points as either P or O. P denotes an obstacle meaning you cannot pass through it while O denotes a valid cell you can pass through.
You can move in any of the four directions i.e. if you are at point (i,j) you can move to
( i , j + 1)
( i , j - 1 )
( i + 1 , j)
( i - 1 , j)
QUICK EXPLANATION:
This turns out to be a standard graph problem. The grid can be considered as a graph where there is an edge between adjacent cells (if they are valid).
EXPLANATION:
The idea is to BFS (breadth first search) on matrix cells. Note that we can always use BFS to find shortest path if graph is unweighted.
Store each cell as a node with their row, column values and distance from the source cell.
Start BFS with a source cell.
Make a visited array with all having “false” values except ‘O’cells which are assigned “true” values as they can not be traversed.
Keep updating distance from source value in each move.
Return distance when destination is met, else return -1 (no path exists in between source and destination).
SOLUTIONS:
Setters Solution
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
using namespace std;
const int MAXN = 100001;
string s[100000];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
int main()
{
int n,m;
cin>>n>>m;
pair<int,int> st,en;
for(int i = 0;i<n;i++){
cin>>s[i];
for(int j = 0;j<m;j++){
if(s[i][j] == 'V'){
st = {i,j};
}
if(s[i][j] == 'S'){
en = {i,j};
}
}
}
vector<vector<int>> dist(n,vector<int>(m,1e8));
dist[st.first][st.second] = 0;
queue<pair<int,int>> q;
q.push(st);
while(!q.empty()){
int i,j;
tie(i,j) = q.front();
q.pop();
for(int k =0;k<4;k++){
int ni = i+dx[k];
int nj = j+ dy[k];
if(isvalid(ni,nj,n,m) and dist[ni][nj]>dist[i][j]+1){
dist[ni][nj] = dist[i][j] + 1;
q.push(make_pair(ni,nj));
}
}
}
cout<<dist[en.first][en.second]<<endl;
}