昨天刷到一個(gè)很有意思的題目柳击，489.?Robot Room Cleaner， 是hard題片习，我順便看了下半年內(nèi)的公司選這道題目面試的tag, google facebook這種大廠非常多次捌肴。?
這道題做完就會(huì)想會(huì)不會(huì)家里的掃地機(jī)器人也是這個(gè)算法？你猜你家里的掃地機(jī)器人用的是什么算法呢藕咏？哈哈肯定不是這個(gè)状知。
這個(gè)題目乍一看感覺(jué)有點(diǎn)難，因?yàn)闄C(jī)器人是randomly安排起始點(diǎn)的孽查，但是題目很清楚地表示了用一個(gè)m*n的方格子來(lái)作為maze饥悴，這個(gè)就相當(dāng)于給了很多限制。然后后面還有機(jī)器人到達(dá)一個(gè)方塊的時(shí)候，如何知道是面朝什么方向的呢西设？
這道題的leetcode solution給我們指向了一個(gè)maze algorithm的wiki瓣铣，solution用的就是right-hand rule。這個(gè)就讓思路很清晰了贷揽。另外solution比較tricky的就是仍然用一個(gè)矩陣來(lái)記錄visited node 來(lái)幫助backtrack棠笑。以起始點(diǎn)為原坐標(biāo)，構(gòu)建矩陣擒滑。
solution:
class Solution {
? ? int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
? ? Set<Pair<Integer, Integer>> visited = new HashSet<>();
? ? Robot robot;
? ? private void goback() {
? ? ? ? robot.turnRight();
? ? ? ? robot.turnRight();
? ? ? ? robot.move();
? ? ? ? robot.turnRight();
? ? ? ? robot.turnRight();
? ? }
? ? private void backtrack(int i, int j, int dir) {
? ? ? ? visited.add(new Pair(i, j));
? ? ? ? robot.clean();
? ? ? ? for(int d = 0;d<4;d++) {
? ? ? ? ? ? int del = (dir + d)%4; // 非常好的去解決方向的問(wèn)題
? ? ? ? ? ? int newI = i + directions[del][0];
? ? ? ? ? ? int newJ = j + directions[del][1];
? ? ? ? ? ? if(!visited.contains(new Pair(newI, newJ)) && robot.move()) {
? ? ? ? ? ? ? ? backtrack(newI, newJ, del);
? ? ? ? ? ? ? ? goback();
? ? ? ? ? ? }
? ? ? ? ? ? robot.turnRight();
? ? ? ? }
? ? }
? ? public void cleanRoom(Robot robot) {
? ? ? ? this.robot = robot;
? ? ? ? backtrack(0,0,0);
? ? }
}
time complexity:?O(N?M), where?N is a number of cells in the room and M?is a number of obstacles.
space complexity: O(N-M)
比較接近的一道題：?130.?Surrounded Regions 腐晾， 比較輕松的做法就是原地修改值，然后再改回來(lái)丐一。
