In this HackerEarth Cross the river problem solution You are required to cross a river to reach your destination. The streamflow of the river was fast, therefore, you cannot cross the river by swimming.
The river is available at the X-axis and its boundary is marked by Y coordinates, from y = A to y = B.
------------------------------------------------------------------------------- (y = A)
..................................................................................................
..................................................................................................
..................................................................................................
-------------------------------------------------------------------------------- (y = B)
You are provided with some rocks along with their centers and radius respectively. Currently, you are standing on the shore y = B. You cannot jump between rocks but can move from one rock to another if both rocks overlap at some point. You are required to determine whether you will be able to cross the river by using rocks or not. If you can cross the river, then print the minimum number of rocks that are required to cross the river. Otherwise, print -1.
HackerEarth Cross the river problem solution.
#include<bits/stdc++.h>
using namespace std;
#define TRACE
#ifdef TRACE
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define TR(...)
#endif
typedef long long LL;
typedef pair<int,int> II;
typedef vector<int> VI;
typedef vector<II> VII;
#define REP(i,i1,n) for(int i=i1;i<n;i++)
#define REPB(i,i1,n) for(int i=i1;i>=n;i--)
#define PB push_back
#define MP make_pair
#define ALL(c) (c).begin(),(c).end()
#define F first
#define S second
#define log2 0.30102999566398119521373889472449L
#define SZ(a) (int)a.size()
#define EPS 1e-12
#define MOD 1000000007
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define SI(c) scanf("%d",&c)
#define SLL(c) scanf("%lld",&c)
#define PIN(c) printf("%d\n",c)
#define PLLN(c) printf("%lld\n",c)
#define N 200010
#define endl '\n'
#define FILL(ar,vl) for(int i=0;i<N;i++)ar[i]=vl
#define FILL2(ar,vl) for(int i=0;i<N;i++)for(int j=0;j<N;j++)ar[i][j]=vl
inline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }
inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }
LL powmod(LL a,LL b) { if(b==0)return 1; LL x=powmod(a,b/2); LL y=(x*x)%MOD; if(b%2) return (a*y)%MOD; return y%MOD; }
//--------------------------MAIN CODE STARTS HERE----------------
#define MAX 1e9
int main() {
int T;
SI(T);
while(T--) {
int A, B, n;
SI(n);
int X[n], Y[n], R[n], vis[N], mark_1[n], mark_2[n], dist[n];
memset(vis,0,sizeof(vis));
memset(mark_1,0,sizeof(mark_1));
memset(mark_2,0,sizeof(mark_2));
vector<int> g[n];
for(int i = 0; i < n; i ++) {
SI(X[i]);SI(Y[i]);SI(R[i]);
}
SI(A);SI(B);
for(int i = 0; i < n ; i ++) {
for(int j = i + 1; j < n; j ++) {
LL dist_1 = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
LL dist_2 =(R[i] + R[j]) * (R[i] + R[j]);
if(dist_1 <= dist_2) { // constructing edge between overlapping rocks
g[i].push_back(j);
g[j].push_back(i);
}
}
}
// checking which of the rocks overlap with the shore (y=a) && (y=b)
for(int i = 0; i < n; i++) {
if(abs(Y[i] - A) <= R[i]) mark_1[i] = 1;
if(abs(Y[i] - B) <= R[i]) mark_2[i] = 1;
}
priority_queue< II,vector<II>,greater<II> > Q;
for(int i = 0; i < n; i++) dist[i] = MAX;
for(int i = 0; i < n; i++) {
if(mark_2[i]) {
Q.push(MP(1,i));
dist[i] = 1;
}
}
int ans = MAX;
while(!Q.empty()) {
II idx = Q.top();
int cost = idx.first, id = idx.second;
Q.pop();
if(vis[id]) continue;
vis[id] = 1;
if(mark_1[id]) {
ans = min(ans,cost);
}
for(int i = 0; i < g[id].size(); i ++) {
if(dist[g[id][i]] > cost + 1) {
dist[g[id][i]] = cost + 1;
Q.push(MP(cost + 1,g[id][i]));
}
}
}
if(ans!=MAX)
PIN(ans);
else PIN(-1);
}
return 0;
}Second solution
#include<bits/stdc++.h>
#define piii pair<int,pair<int,int> >
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define sfd(n) scanf("%d",&n)
#define MAXX 1000000000
#define MINX -1000000000
using namespace std;
pair<pair<int,int>,int> pt[5005];
vector<int> adj[5005];
int s,d;
int up[5005],down[5005];
queue<int> q;
bool Intersects(int x1,int y1,int r1,int x2,int y2,int r2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(r1+r2)*(r1+r2);
}
void bfs(int arr[])
{
while(!q.empty())
{
int k=q.front();
q.pop();
int a=pt[k].fi.fi;
int b=pt[k].fi.se;
for(int j=0;j<adj[k].size();j++)
{
if(arr[adj[k][j]]>arr[k]+1)
{
arr[adj[k][j]]=arr[k]+1;
q.push(adj[k][j]);
}
}
}
}
int main()
{
int t;
sfd(t);
assert(1<=t&&t<=10);
while(t--)
{
int n;
sfd(n);
assert(1<=n&&n<=5000);
for(int i=0;i<n;i++)
{
int x,y,r;
sfd(x);
sfd(y);
sfd(r);
assert(MINX<=x&&x<=MAXX);
assert(MINX<=y&&y<=MAXX);
assert(1<=r&&r<=MAXX);
pt[i]=mkp(mkp(x,y),r);
}
sfd(s);
sfd(d);
assert(MINX<=s&&s<=MAXX);
assert(MINX<=d&&d<=MAXX);
assert(s>=d);
for(int i=0;i<n;i++)
{
adj[i].clear();
up[i]=INT_MAX;
down[i]=INT_MAX;
}
for(int i=0;i<(n-1);i++)
{
for(int j=i+1;j<n;j++)
{
if(Intersects(pt[i].fi.fi,pt[i].fi.se,pt[i].se,pt[j].fi.fi,pt[j].fi.se,pt[j].se))
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
for(int i=0;i<n;i++)
{
if(pt[i].fi.se-pt[i].se<=d)
{
up[i]=1;
q.push(i);
}
}
bfs(up);
for(int i=0;i<n;i++)
{
if(pt[i].fi.se+pt[i].se>=s)
{
down[i]=1;
q.push(i);
}
}
bfs(down);
int ans=INT_MAX;
for(int i=0;i<n;i++)
{
if(up[i]!=INT_MAX && down[i]!=INT_MAX)
ans=min(ans,up[i]+down[i]-1);
}
if(ans==INT_MAX)
printf("-1\n");
else
printf("%d\n",ans);
}
}
0 Comments