Horje
Check if traversal from first co-ordinate to all coordinates possible or not

Given array A[][2] of size N representing co-ordinates and integer D, the task for this problem is to print a binary string of size N whose i’th character is ‘1’ if it is possible to travel from initial co-ordinate to i’th co-ordinate else ‘0’. Start Traversal from first co-ordinate of array A[][2] and Traversal from one co-ordinate (x1, y1) to another co-ordinate (x2, y2) is possible if sqrt((x2&#x200b&#x2212x1&#x200b)2 + (y2 – y1)2&#x200b) &#x2264 D.

Examples:

Input: A[][2] = {{2, -1}, {3, 1}, {8, 8}, {0, 5}}, D = 5
Output: 1101
Explanation:

  • The distance between co-ordinate 1 and co-ordinate 2 is square root of 5 which is less than equal to 5, so co-ordinate 2 gets visited.
  • Also, the distance between co-ordinate 2 and co-ordinate 4 is square root of 25 which is less than equal to 5, so co-ordinate 4 gets visited.
  • co-ordinate 3 has no one within a distance of 5, so it will not get visited.

Input: A[][2] = {{0, 0}, {-1000, -1000}, {1000, 1000}}, D = 1
Output: 100

Approach: To solve the problem follow the below idea:

Depth-First-Search can be used to solve the above problem. We can visualize the co-ordinate-plane as a graph with every co-ordinate as a node.

Below are the steps for the above approach: 

  • Create an empty string ans.
  • Create a visited array vis[N] with all elements initialized to zero.
  • Create dfs() function that takes one parameter which is co-ordinate that is being visited:
    • Mark it as 1 that is visited vis[i] = 1.
    • Iterate all co-ordinates apart from the current and check whether it is unvisited and distance between the co-ordinate that is being iterated and the current co-ordinate is less than equal to D if it is true to call dfs() function for the co-ordinate of the current iteration.
  • Call dfs(0, vis, A, N, D) function with initial co-ordinate 0.
  • Iterate for i from 0 to N – 1 if vis[i] is equal to 1 push character ‘1‘ in a string else ‘0’.
  • return string ans.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// dfs function to find whether given
// co-ordinates can be visited or not
// from starting co-ordinate 1
void dfs(int v, vector<int>& vis, int A[][2], int N, int D)
{
 
    // Mark it visited
    vis[v] = 1;
 
    // Check which other co-ordinates can
    // be visited from current co-ordinate
    for (int i = 0; i < N; i++) {
 
        // If i is equal to current
        // co-ordinate skip the iteration
        if (i == v)
            continue;
 
        // Distance from co-ordinate i to v
        int dist = (A[v][0] - A[i][0]) * (A[v][0] - A[i][0])
                   + (A[v][1] - A[i][1], 2)
                         * (A[v][1] - A[i][1], 2);
 
        // Distance between them is less
        // than D and it was not
        // visited before
        if (dist <= (D * D) and vis[i] == 0)
            dfs(i, vis, A, N, D);
    }
}
 
// Function to find whether given
// co-ordinates can be visited or not
// from starting co-ordinate 1
string canPossibleToVisit(int A[][2], int N, int D)
{
 
    // Answer string
    string ans = "";
 
    // Visited array that will
    // keep track of
    vector<int> vis(N, 0);
 
    // Call of dfs function
    dfs(0, vis, A, N, D);
 
    for (int i = 0; i < N; i++) {
 
        // If ith co-ordinate can
        // be visited
        if (vis[i] == 1)
            ans.push_back('1');
 
        // If it cannnot be visited
        else
            ans.push_back('0');
    }
 
    // Return answer
    return ans;
}
 
// Driver Code
int32_t main()
{
 
    // Input 1
    int N = 4, D = 5;
    int A[][2]
        = { { 2, -1 }, { 3, 1 }, { 8, 8 }, { 0, 5 } };
 
    // Function Call
    cout << canPossibleToVisit(A, N, D) << endl;
 
    // Input 2
    int N1 = 3, D1 = 1;
    int A1[][2]
        = { { 0, 0 }, { -1000, -1000 }, { 1000, 1000 } };
 
    // Function Call
    cout << canPossibleToVisit(A1, N1, D1) << endl;
 
    return 0;
}

Java

//Java Code for the above approach
import java.util.ArrayList;
import java.util.List;
 
public class GFG {
 
    // DFS function to find whether given
    // coordinates can be visited or not
    // from starting coordinate 1
    static void dfs(int v, List<Integer> vis, int[][] A, int N, int D) {
        vis.set(v, 1);
 
        for (int i = 0; i < N; i++) {
            if (i == v) {
                continue;
            }
 
            // Calculate the distance between
            // the current coordinate and coordinate i
            int dist = (A[v][0] - A[i][0]) * (A[v][0] - A[i][0]) +
                       (A[v][1] - A[i][1]) * (A[v][1] - A[i][1]);
 
            // If the distance is less than or equal to D
            // and coordinate i has not been visited, perform DFS
            if (dist <= (D * D) && vis.get(i) == 0) {
                dfs(i, vis, A, N, D);
            }
        }
    }
 
    // Function to find whether given coordinates
    // can be visited or not from starting coordinate 1
    static String canPossibleToVisit(int[][] A, int N, int D) {
        StringBuilder ans = new StringBuilder();
        List<Integer> vis = new ArrayList<>(N);
 
        // Initialize the visited list
        for (int i = 0; i < N; i++) {
            vis.add(0);
        }
 
        // Call the DFS function
        dfs(0, vis, A, N, D);
 
        // Build the answer string based on the visited list
        for (int i = 0; i < N; i++) {
            if (vis.get(i) == 1) {
                ans.append('1');
            } else {
                ans.append('0');
            }
        }
 
        return ans.toString();
    }
 
    public static void main(String[] args) {
        int N = 4, D = 5;
        int[][] A = { { 2, -1 }, { 3, 1 }, { 8, 8 }, { 0, 5 } };
        System.out.println(canPossibleToVisit(A, N, D));
 
        int N1 = 3, D1 = 1;
        int[][] A1 = { { 0, 0 }, { -1000, -1000 }, { 1000, 1000 } };
        System.out.println(canPossibleToVisit(A1, N1, D1));
    }
}

Python3

# Python3 code to implement the approach
 
# dfs function to find whether given
# co-ordinates can be visited or not
# from starting co-ordinate 1
def dfs(v, vis, A, N, D):
    # Mark it visited
    vis[v] = 1
 
    # Check which other co-ordinates can
    # be visited from current co-ordinate
    for i in range(N):
        # If i is equal to current
        # co-ordinate skip the iteration
        if i == v:
            continue
 
        # Distance from co-ordinate i to v
        dist = (A[v][0] - A[i][0]) ** 2 + (A[v][1] - A[i][1]) ** 2
 
        # Distance between them is less
        # than D and it was not visited before
        if dist <= D ** 2 and vis[i] == 0:
            dfs(i, vis, A, N, D)
 
# Function to find whether given
# co-ordinates can be visited or not
# from starting co-ordinate 1
def canPossibleToVisit(A, N, D):
    # Answer string
    ans = ""
 
    # Visited array that will keep track of
    vis = [0] * N
 
    # Call of dfs function
    dfs(0, vis, A, N, D)
 
    for i in range(N):
        # If ith co-ordinate can be visited
        if vis[i] == 1:
            ans += '1'
        # If it cannot be visited
        else:
            ans += '0'
 
    # Return answer
    return ans
 
# Driver Code
if __name__ == "__main__":
    # Input 1
    N, D = 4, 5
    A = [[2, -1], [3, 1], [8, 8], [0, 5]]
 
    # Function Call
    print(canPossibleToVisit(A, N, D))
 
    # Input 2
    N1, D1 = 3, 1
    A1 = [[0, 0], [-1000, -1000], [1000, 1000]]
 
    # Function Call
    print(canPossibleToVisit(A1, N1, D1))
 
# This code is contributed by Susobhan Akhuli

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
public class GFG {
    // dfs function to find whether given
    // co-ordinates can be visited or not
    // from starting co-ordinate 1
    static void dfs(int v, List<int> vis, int[, ] A, int N,
                    int D)
    {
        // Mark it visited
        vis[v] = 1;
 
        // Check which other co-ordinates can
        // be visited from current co-ordinate
        for (int i = 0; i < N; i++) {
            // If i is equal to current
            // co-ordinate skip the iteration
            if (i == v)
                continue;
 
            // Distance from co-ordinate i to v
            int dist
                = (A[v, 0] - A[i, 0]) * (A[v, 0] - A[i, 0])
                  + (A[v, 1] - A[i, 1])
                        * (A[v, 1] - A[i, 1]);
 
            // Distance between them is less
            // than D and it was not
            // visited before
            if (dist <= (D * D) && vis[i] == 0)
                dfs(i, vis, A, N, D);
        }
    }
 
    // Function to find whether given
    // co-ordinates can be visited or not
    // from starting co-ordinate 1
    static string CanPossibleToVisit(int[, ] A, int N,
                                     int D)
    {
        // Answer string
        string ans = "";
 
        // Visited array that will
        // keep track of visited co-ordinates
        List<int> vis = new List<int>(new int[N]);
 
        // Call of dfs function
        dfs(0, vis, A, N, D);
 
        for (int i = 0; i < N; i++) {
            // If ith co-ordinate can be visited
            if (vis[i] == 1)
                ans += "1";
            // If it cannot be visited
            else
                ans += "0";
        }
 
        // Return answer
        return ans;
    }
 
    // Driver Code
    static void Main(string[] args)
    {
        // Input 1
        int N = 4, D = 5;
        int[, ] A
            = { { 2, -1 }, { 3, 1 }, { 8, 8 }, { 0, 5 } };
 
        // Function Call
        Console.WriteLine(CanPossibleToVisit(A, N, D));
 
        // Input 2
        int N1 = 3, D1 = 1;
        int[, ] A1 = { { 0, 0 },
                       { -1000, -1000 },
                       { 1000, 1000 } };
 
        // Function Call
        Console.WriteLine(CanPossibleToVisit(A1, N1, D1));
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// Javascript code to implement the approach
 
// dfs function to find whether given
// co-ordinates can be visited or not
// from starting co-ordinate 1
function dfs(v, vis, A, N, D) {
    // Mark it visited
    vis[v] = 1;
 
    // Check which other co-ordinates can
    // be visited from the current co-ordinate
    for (let i = 0; i < N; i++) {
        // If i is equal to the current
        // co-ordinate, skip the iteration
        if (i === v)
            continue;
 
        // Distance from co-ordinate i to v
        let dist =
            (A[v][0] - A[i][0]) * (A[v][0] - A[i][0]) +
            (A[v][1] - A[i][1]) * (A[v][1] - A[i][1]);
 
        // Distance between them is less
        // than D and it was not
        // visited before
        if (dist <= D * D && vis[i] === 0)
            dfs(i, vis, A, N, D);
    }
}
 
// Function to find whether given
// co-ordinates can be visited or not
// from the starting co-ordinate 1
function canPossibleToVisit(A, N, D) {
    // Answer string
    let ans = "";
 
    // Visited array that will
    // keep track of
    let vis = Array(N).fill(0);
 
    // Call the dfs function
    dfs(0, vis, A, N, D);
 
    for (let i = 0; i < N; i++) {
        // If the ith co-ordinate can
        // be visited
        if (vis[i] === 1)
            ans += '1';
        // If it cannot be visited
        else
            ans += '0';
    }
 
    // Return answer
    return ans;
}
 
// Driver Code
// Input 1
let N = 4, D = 5;
let A = [[2, -1], [3, 1], [8, 8], [0, 5]];
 
// Function Call
console.log(canPossibleToVisit(A, N, D) + "<br/>");
 
// Input 2
let N1 = 3, D1 = 1;
let A1 = [[0, 0], [-1000, -1000], [1000, 1000]];
 
// Function Call
console.log(canPossibleToVisit(A1, N1, D1));
 
// This code is contributed by Susobhan Akhuli

Output

1101
100

Time Complexity: O(N * N)  
Auxiliary Space: O(N)

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Merge Sort Interview Questions and Answers Merge Sort Interview Questions and Answers
Lexicographically shortest valid Subset selection Lexicographically shortest valid Subset selection
Tree Data Structure Tree Data Structure
What is the difference between an undirected and a directed Graph? What is the difference between an undirected and a directed Graph?
Applications, Advantages and Disadvantages of Radix Sort Applications, Advantages and Disadvantages of Radix Sort

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje