Path in a Rectangle with Circles | C ++ program to find out path in a rectangle containing circles . ; Function to find out if there is any possible path or not . ; Take an array of m * n size and initialize each element to 0. ; Now using Pythagorean theorem find if a cell touches or within any circle or not . ; If the starting cell comes within any circle return false . ; Now use BFS to find if there is any possible path or not . Initialize the queue which holds the discovered cells whose neighbors are not discovered yet . ; Discover cells until queue is not empty ; Discover the eight adjacent nodes . check top - left cell ; check top cell ; check top - right cell ; check left cell ; check right cell ; check bottom - left cell ; check bottom cell ; check bottom - right cell ; Now if the end cell ( i . e . bottom right cell ) is 1 ( reachable ) then we will send true . ; Driver Program ; Test case 1 ; Function call ; Test case 2 ; Function call
#include <iostream> NEW_LINE #include <math.h> NEW_LINE #include <vector> NEW_LINE using namespace std ; bool isPossible ( int m , int n , int k , int r , vector < int > X , vector < int > Y ) { int rect [ m ] [ n ] = { 0 } ; for ( int i = 0 ; i < m ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { for ( int p = 0 ; p < k ; p ++ ) { if ( sqrt ( ( pow ( ( X [ p ] - 1 - i ) , 2 ) + pow ( ( Y [ p ] - 1 - j ) , 2 ) ) ) <= r ) { rect [ i ] [ j ] = -1 ; } } } } if ( rect [ 0 ] [ 0 ] == -1 ) return false ; vector < vector < int > > qu ; rect [ 0 ] [ 0 ] = 1 ; qu . push_back ( { 0 , 0 } ) ; while ( ! qu . empty ( ) ) { vector < int > arr = qu . front ( ) ; qu . erase ( qu . begin ( ) ) ; int elex = arr [ 0 ] ; int eley = arr [ 1 ] ; if ( ( elex > 0 ) && ( eley > 0 ) && ( rect [ elex - 1 ] [ eley - 1 ] == 0 ) ) { rect [ elex - 1 ] [ eley - 1 ] = 1 ; vector < int > v = { elex - 1 , eley - 1 } ; qu . push_back ( v ) ; } if ( ( elex > 0 ) && ( rect [ elex - 1 ] [ eley ] == 0 ) ) { rect [ elex - 1 ] [ eley ] = 1 ; vector < int > v = { elex - 1 , eley } ; qu . push_back ( v ) ; } if ( ( elex > 0 ) && ( eley < n - 1 ) && ( rect [ elex - 1 ] [ eley + 1 ] == 0 ) ) { rect [ elex - 1 ] [ eley + 1 ] = 1 ; vector < int > v = { elex - 1 , eley + 1 } ; qu . push_back ( v ) ; } if ( ( eley > 0 ) && ( rect [ elex ] [ eley - 1 ] == 0 ) ) { rect [ elex ] [ eley - 1 ] = 1 ; vector < int > v = { elex , eley - 1 } ; qu . push_back ( v ) ; } if ( ( eley < n - 1 ) && ( rect [ elex ] [ eley + 1 ] == 0 ) ) { rect [ elex ] [ eley + 1 ] = 1 ; vector < int > v = { elex , eley + 1 } ; qu . push_back ( v ) ; } if ( ( elex < m - 1 ) && ( eley > 0 ) && ( rect [ elex + 1 ] [ eley - 1 ] == 0 ) ) { rect [ elex + 1 ] [ eley - 1 ] = 1 ; vector < int > v = { elex + 1 , eley - 1 } ; qu . push_back ( v ) ; } if ( ( elex < m - 1 ) && ( rect [ elex + 1 ] [ eley ] == 0 ) ) { rect [ elex + 1 ] [ eley ] = 1 ; vector < int > v = { elex + 1 , eley } ; qu . push_back ( v ) ; } if ( ( elex < m - 1 ) && ( eley < n - 1 ) && ( rect [ elex + 1 ] [ eley + 1 ] == 0 ) ) { rect [ elex + 1 ] [ eley + 1 ] = 1 ; vector < int > v = { elex + 1 , eley + 1 } ; qu . push_back ( v ) ; } } return ( rect [ m - 1 ] [ n - 1 ] == 1 ) ; } int main ( ) { int m1 = 5 , n1 = 5 , k1 = 2 , r1 = 1 ; vector < int > X1 = { 1 , 3 } ; vector < int > Y1 = { 3 , 3 } ; if ( isPossible ( m1 , n1 , k1 , r1 , X1 , Y1 ) ) cout << " Possible " << endl ; else cout << " Not ▁ Possible " << endl ; int m2 = 5 , n2 = 5 , k2 = 2 , r2 = 1 ; vector < int > X2 = { 1 , 1 } ; vector < int > Y2 = { 2 , 3 } ; if ( isPossible ( m2 , n2 , k2 , r2 , X2 , Y2 ) ) cout << " Possible " << endl ; else cout << " Not ▁ Possible " << endl ; return 0 ; }