C++ DFS, 26 ms


  • 0
    X

    My c++ DFS: roll four directions according to d, l, r, u, order. use visited[m][n] matrix to remember if the path are visited or not.

    void findShortestWayDfs(vector<vector<int>> &maze, int m, int n, vector<int>& hole, int x, int y, 
    						vector<vector<bool>> &visited, int dist, int &minDist, string &curr, string &res )
    {
    	if (dist >= minDist) return;
    	if (visited[x][y]) return;
    
    	visited[x][y] = true;
    	vector<pair<int, int>> incr = { {1,0},{0,-1},{0,1},{-1,0} };
    	vector<char> dir = { 'd','l','r','u' };
    
    	for (int k = 0; k < 4; ++k)
    	{
    		int step = 0;
    		int i = x;
    		int j = y;
    		int d_i = incr[k].first;
    		int d_j = incr[k].second;
    		curr.push_back(dir[k]);
    		bool found = false;
    
    		while (i+ d_i < m && i+ d_i >=0 && j+ d_j >=0 && j+ d_j <n && maze[i+ d_i][j+ d_j] == 0)
    		{
    			++step;
    			i += incr[k].first;
    			j += incr[k].second;
    			if (visited[i][j]) // it is visited before, so it is not the shortest
    			{
    				found = true;
    				break;
    			}
    			if (i == hole[0] && j == hole[1]) // reach the hole, candidate for min dist
    			{
    				if (dist + step < minDist)
    				{
    					res = curr;
    					minDist = dist + step;
    					found = true;
    					break;
    				}
    			}
    		}
    		if (!found && step > 0)
    			findShortestWayDfs(maze, m, n, hole, i, j, visited, dist + step, minDist, curr, res);
    		curr.pop_back();
    	}
    	
    	visited[x][y] = false;
    }
    
    
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole)
    {
    	int m = maze.size();
    	int n = maze[0].size();
    
    	vector<vector<bool>> visited(m, vector<bool>(n, false));
    
    
    	int minDist = m*n;
    	string curr, res;
    	findShortestWayDfs(maze, m, n, hole, ball[0], ball[1], visited, 0, minDist, curr, res);
    
    	if (res.length() == 0)
    		res = "impossible";
    
    	return res;
    }
    

Log in to reply
 

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