505. The Maze II - CPP - Solution


  • 0
    Y
    // 505. The Maze II
    // https://leetcode.com/problems/the-maze-ii/
    #include <iostream>
    #include <cassert>
    #include <climits>
    #include <algorithm>
    #include <vector>
    #include <list>
    #include <set>
    #include <iterator>
    using namespace std;
    // BEGIN: https://discuss.leetcode.com/topic/77472/similar-to-the-maze-easy-understanding-java-bfs-solution
    class Solution {
    public:
    	int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    		if (maze.empty()) {
    			return 0;
    		}
    		const int p = maze.size();
    		if (maze.front().empty()) {
    			return 0;
    		}
    		const int q = maze.front().size();
    		list<vector<int>> queue;
    		queue.push_back(start);
    		const vector<int> dx{-1, 0, 1, 0};
    		const vector<int> dy{0, -1, 0, 1};
    		vector<vector<int>> distance(p, vector<int>(q, -1));
    		distance[start[0]][start[1]] = 0;
    		while (!queue.empty()) {
    			const vector<int> frontOfQueue = queue.front();
    			queue.pop_front();
    			const int currentX = frontOfQueue[0];
    			const int currentY = frontOfQueue[1];
    			const int currentD = distance[currentX][currentY];
    			for (int i = 0; i < 4; i++) {
    				int nextX = currentX;
    				int nextY = currentY;
    				int nextD = currentD;
    				while (nextX + dx[i] >= 0 && nextX + dx[i] < p && nextY + dy[i] >= 0 && nextY + dy[i] < q && maze[nextX + dx[i]][nextY + dy[i]] == 0) {
    					nextX += dx[i];
    					nextY += dy[i];
    					nextD++;
    				}
    				const vector<int> nextPoint{nextX, nextY};
    				if (distance[nextX][nextY] < 0) {
    					queue.push_back(nextPoint);
    					distance[nextX][nextY] = nextD;
    					continue;
    				}
    				if (nextD < distance[nextX][nextY]) {
    					queue.push_back(nextPoint);
    					distance[nextX][nextY] = nextD;
    					continue;
    				}
    			}
    		}
    		return distance[destination[0]][destination[1]];
    	}
    };
    // END: https://discuss.leetcode.com/topic/77472/similar-to-the-maze-easy-understanding-java-bfs-solution
    int main(void) {
    	Solution solution;
    	vector<vector<int>> maze;
    	vector<int> start;
    	vector<int> destination;
    	int result = 0;
    
    	maze = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}};
    	start = {0, 4};
    	destination = {4, 4};
    	result = solution.shortestDistance(maze, start, destination);
    	assert(12 == result);
    
    	maze = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}};
    	start = {0, 4};
    	destination = {3, 2};
    	result = solution.shortestDistance(maze, start, destination);
    	assert(-1 == result);
    
    	cout << "\nPassed All\n";
    	return 0;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.