Valid Path Editorial

Practice Problem Link: Valid Path

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You have an n*m matrix with start position at (0, 0) and end position at (n, m).

There are c circles with centres inside the matrix, each with radius r. You are given the centre coordinates (x, y) of each of those circles.

Note: You can move from any point to any of its 8 adjacent neighbours.

Find if there is a way to travel from start to end without touching any of these circles

Approach

Make a matrix of size n*m and initialize every cell to 0. Now find the cells which are not reachable by traversing the matrix and comparing each cell with all the circles and mark those cells as -1. Perform a BFS on the rest of the cells to check whether a path is possible from start to end.

Analysis

• Time Complexity: O(n * m * c)
• Auxiliary Space Complexity: O(n * m)

Implementation

C++

/* This is the Circle class definition
class Circle {
public:
    int x, y; // Co-ordinates of center
    Circle(int x, int y) {
        this->x = x;
        this->y = y;
    }
};
*/
bool distance(int x1, int x2, int y1, int y2, int r) {
	int dx = abs(x2 - x1), dy = abs(y2 - y1);
	dx *= dx;
	dy *= dy;
	if (sqrt (dx + dy) <= r) {
		return true;
	}
	return false;
}
bool hasValidPath(int n, int m, int r, vector<Circle*> &circles) {
    vector<vector<int>> possiblePath (n + 1, vector<int> (m + 1, 0));
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			for(int k = 0; k < circles.size(); k++) {
				if (distance(i, circles[k]->x, j, circles[k]->y, r)) {
					possiblePath[i][j] = - 1;
				}
			}
		}
	}
	if (possiblePath[0][0] == - 1) {
		return false;
	}
	queue<pair<int,int>> reachableNodes;
	reachableNodes.push({0, 0});
	possiblePath[0][0] = 1;
	while(!reachableNodes.empty()) {
		pair<int, int> currNode = reachableNodes.front();
		int x = currNode.first;
		int y = currNode.second;
		reachableNodes.pop();
		for(int i = max(0, x - 1); i <= min(n, x + 1); i++) {
			for (int j = max(0, y - 1); j <= min(m, y + 1); j++) {
				if(possiblePath[i][j] == 0) {
					possiblePath[i][j] = 1;
					reachableNodes.push({i, j});
				}
			}
		}
	}
	if (possiblePath[n][m] == 1) {
		return true;
	}
	return false;
}

Java

/* This is the Circle class definition
class Circle {
	public int x, y; // Co-ordinates of center
    public Circle(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
*/

class Solution {
	class Pair {
		int first, second;
		Pair(int x, int y) {
			first = x;
			second = y;
		}
	}
	boolean distance(int x1, int x2, int y1, int y2, int r) {
		int dx = Math.abs(x2 - x1), dy = Math.abs(y2 - y1);
		dx *= dx;
		dy *= dy;
		if (Math.sqrt (dx + dy) <= r) {
			return true;
		}
		return false;
	}
	boolean hasValidPath(int n, int m, int r, Circle[] circles) {
        int[][] possiblePath = new int[n + 1][m + 1];
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				for(int k = 0; k < circles.length; k++) {
					if (distance(i, circles[k].x, j, circles[k].y, r)) {
						possiblePath[i][j] = - 1;
					}
				}
			}
		}
		if (possiblePath[0][0] == - 1) {
			return false;
		}
		Queue<Pair> reachableNodes = new LinkedList<Pair>();
		reachableNodes.add(new Pair(0, 0));
		possiblePath[0][0] = 1;
		while(!reachableNodes.isEmpty()) {
			Pair currNode = reachableNodes.poll();
			int x = currNode.first;
			int y = currNode.second;
			for(int i = Math.max(0, x - 1); i <= Math.min(n, x + 1); i++) {
				for (int j = Math.max(0, y - 1); j <= Math.min(m, y + 1); j++) {
					if(possiblePath[i][j] == 0) {
						possiblePath[i][j] = 1;
						reachableNodes.add(new Pair(i, j));
					}
				}
			}
			
		}
		if (possiblePath[n][m] == 1) {
			return true;
		}
		return false;
	}
}