➤ Problem Link : 242C. King's Path
✅ C++ Solution :
#include<bits/stdc++.h> using namespace std; #define ll long long int #define pp pair<ll,ll> #define mp make_pair int lt[]={-1,-1,-1,1,1,1,0,0}; int rt[]={-1,0,1,-1,0,1,-1,1}; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll x0,y0,x1,y1; set<pp> st; cin>>x0>>y0>>x1>>y1; ll n,r,a,b; cin>>n; for(ll i=0;i<n;i++) { cin>>r>>a>>b; for(ll j=a;j<=b;j++) { if(st.find(mp(r,j))==st.end()) st.insert(mp(r,j)); } } ll cnt=0; st.erase(mp(x0,y0)); queue<pp> q; pp p; q.push(mp(x0,y0)); int x,y; bool f=0; while(!q.empty()) { int s=q.size(); while(s--) { p=q.front(); q.pop(); if(p==mp(x1,y1)) { f=1; break; } for(int i=0;i<8;i++) { x=p.first+lt[i]; y=p.second+rt[i]; if(st.find(mp(x,y))!=st.end()) { st.erase(mp(x,y)); q.push(mp(x,y)); } } } if(f) break; cnt++; } if(f) cout<<cnt<<"\n"; else cout<<"-1\n"; }
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!