[LeetCode]Robot Room Cleaner

这道题还是图的问题，遍历不知道任何信息的图，肯定是用DFS的，所以我们要让robot模仿DFS算法来运作。这里要注意的一个问题是，我们能回到的只是之前节点的位置，而不是像递归的时候栈上存的是当前的整个状态，包括所有变量的值。所以我们要处理好每一次从一个节点出去回来的方向，同时我们也需要记录所有visited过的节点，尽管我们不知道图的任何信息，包括初始位置和方向，我们以当前位置为(0, 0)即可，并且选一个方向为起始方向，然后之后到达的每一个节点，我们方向更新坐标即可。
我们可以自行规定，每当我们进入一个新的节点：

1. 先turnLeft()遍历当前方向的节点
2. 之后每次turnRight()，重复四次，保证我们遍历所有方向的子节点（这里要四次是因为起始节点需要遍历四个方向，非其实节点只需要遍历非入射方向）
3. 最后turnLeft()，面向入射节点

注意第二步当中，有两种情况，如果当前方向子节点是wall，我们直接turnRight()，否则我们只从子节点回来，是和当初入射的方向相反，所以这个时候我们需要turnLeft()来保证我们下一次访问的是原入射方向右边的子节点。

时间复杂度O(V + E)，做法的话递推课循环都可以，我们两个解法都给出，对图的dfs循环实现不清楚的话，可以参考这篇文章。

递归：

	/**
	* // This is the robot's control interface.
	* // You should not implement it, or speculate about its implementation
	* class Robot {
	* public:
	* // Returns true if the cell in front is open and robot moves into the cell.
	* // Returns false if the cell in front is blocked and robot stays in the current cell.
	* bool move();
	*
	* // Robot will stay in the same cell after calling turnLeft/turnRight.
	* // Each turn will be 90 degrees.
	* void turnLeft();
	* void turnRight();
	*
	* // Clean the current cell.
	* void clean();
	* };
	*/
	class Solution {
	public:
	void cleanRoom(Robot& robot) {
	dfs(robot);
	}
	private:
	vector<pair<int, int>> dirs = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} };
	unordered_set<string> visited;
	int x = 0, y = 0, d = 0;
	void dfs(Robot& robot)
	{
	if (visited.count(to_string(x) + ":" + to_string(y)))
	{
	//go back to previous point
	turnRight(robot);
	turnRight(robot);
	return;
	}
	robot.clean();
	visited.insert(to_string(x) + ":" + to_string(y));
	turnLeft(robot);
	for (int i = 0; i < 4; ++i)
	{
	if (!moveForward(robot))
	{
	turnRight(robot);
	continue;
	}
	dfs(robot);
	//return back to previous location
	moveForward(robot);
	//when it comes back from dfs point
	//it will be opposite direction to
	//the direction when we goes in
	turnLeft(robot);
	}
	//change the direction so we are facing
	//going in point
	turnLeft(robot);
	}
	void turnLeft(Robot& robot)
	{
	robot.turnLeft();
	d = (d + 3) % 4;
	}
	void turnRight(Robot& robot)
	{
	robot.turnRight();
	d = (d + 1) % 4;
	}
	bool moveForward(Robot& robot)
	{
	bool canReach = robot.move();
	if (canReach)
	{
	x += dirs[d].first;
	y += dirs[d].second;
	}
	return canReach;
	}
	};

view raw Robot Room Cleaner_recursive.cpp hosted with ❤ by GitHub

循环：

	/**
	* // This is the robot's control interface.
	* // You should not implement it, or speculate about its implementation
	* class Robot {
	* public:
	* // Returns true if the cell in front is open and robot moves into the cell.
	* // Returns false if the cell in front is blocked and robot stays in the current cell.
	* bool move();
	*
	* // Robot will stay in the same cell after calling turnLeft/turnRight.
	* // Each turn will be 90 degrees.
	* void turnLeft();
	* void turnRight();
	*
	* // Clean the current cell.
	* void clean();
	* };
	*/
	class Solution {
	public:
	void cleanRoom(Robot& robot) {
	stack<int> st;
	st.push(0);
	clean(robot);
	while(st.size())
	{
	int key = st.top();
	if(key < 4)
	{
	if(!key)turnLeft(robot);
	st.pop();
	st.push(key + 1);
	if(moveForward(robot)){clean(robot);st.push(0);continue;}
	turnRight(robot);
	continue;
	}
	turnLeft(robot);
	robot.move();
	x += dirs[d].first;
	y += dirs[d].second;
	st.pop();
	turnLeft(robot);
	}
	}
	private:
	vector<pair<int, int>> dirs = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} };
	unordered_set<string> visited;
	int x = 0, y = 0, d = 0;
	void clean(Robot& robot)
	{
	visited.insert(to_string(x) + ":" + to_string(y));
	robot.clean();
	}
	void turnLeft(Robot& robot)
	{
	robot.turnLeft();
	d = (d + 3) % 4;
	}
	void turnRight(Robot& robot)
	{
	robot.turnRight();
	d = (d + 1) % 4;
	}
	bool moveForward(Robot& robot)
	{
	bool canReach = robot.move();
	if (canReach)
	{
	x += dirs[d].first;
	y += dirs[d].second;
	if(visited.count(to_string(x) + ":" + to_string(y)))
	{
	x -= dirs[d].first;
	y -= dirs[d].second;
	canReach = false;
	turnRight(robot);
	turnRight(robot);
	robot.move();
	turnRight(robot);
	turnRight(robot);
	}
	}
	return canReach;
	}
	};

view raw Robot Room Cleaner_iterative.cpp hosted with ❤ by GitHub