My AC 26ms C++ DFS


  • 0
    class Solution
    {
    	int M;
    	int N;
    	vector<pair<int, int>> dirs = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
    	bool dfs(vector<vector<int>> &maze, int x, int y)
    	{
    		if (maze[x][y] == 2) return true;
    		maze[x][y] = -1;
    		for (auto &dir : dirs)
    		{
    			int x_next = x, y_next = y;
    			while (x_next + dir.first >= 0 && x_next + dir.first < M
    				&& y_next + dir.second >= 0 && y_next + dir.second < N 
    				&& maze[x_next + dir.first][y_next + dir.second] != 1)
    			{
    				x_next = x_next + dir.first;
    				y_next = y_next + dir.second;
    			}
    			if (maze[x_next][y_next] != -1 && dfs(maze, x_next, y_next))
    				return true;
    		}
    		return false;
    	}
    public:
    	bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination)
    	{
    		M = maze.size();
    		if (M <= 0) return false;
    		N = maze[0].size();
    		maze[destination[0]][destination[1]] = 2;
    		return dfs(maze, start[0], start[1]);
    	}
    };
    

    easy dfs, easy life.


Log in to reply
 

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