扫地机器人

已知扫地机器人有move(), turn_left(k), turn_right(k), clean()方法，机器人能面向东南西北四个方向，move是按当前方向移动一格，如果不能移动返回false; turn_left(k), turn_right(k)是旋转k*90度; 房间里可能有障碍物，机器人并不知道房间的布局，设计算法让扫地机器人清扫房间（走完房间每一格）。

这道题主要是要把题目给抽象出来。简历坐标系，然后把调用API的函数给拉出来单独写。这样的话，题目本身其实就是一个dfs遍历matrix的题目了。

# move(), turn_left(k), turn_right(k), clean()

class Solution(object):
    dirMap = [[1, 0], [0, -1], [-1, 0], [0, 1]]

    def robotClean(self, x, y, room):

        self.visited = set()
        self.visited.add((x, y))
        self.dfs(x, y, room)
        self.dir
        return

    def dfs(self, x, y, room):
        for d, p in self.dirMap:
            i, j = x+d, y+p
            if (i, j) not in self.visited and 0<=i<len(room) and 0<j<=len(room[0]):
                self.visited.add((i, j))
                if self.try_turn_and_move(x, y, i, j):
                    self.clean()
                    self.dfs(i, j, room)
                    self.try_turn_and_move(i, j, x, y)

    def try_turn_and_move(self, x, y, i, j):
        if room[i][j]==1:
            return False

        direction = (i-x, j-y)
        self.dir = direction
        print 'Call API move from '+str((x,y))+'to' + str((i,j))
        return True

    def clean(self):
        print 'call clean API'

room = [
    [0, 0, 0, 1],
    [1, 0, 1, 1],
    [1, 0, 1, 1]
]
s = Solution()
s.robotClean(0, 0, room)

# printing result as follows:
Call API move from (0, 0) to (0, 1)
call clean API
Call API move from (0, 1) to (1, 1)
call clean API
Call API move from (1, 1) to (2, 1)
call clean API
Call API move from (2, 1) to (1, 1)
Call API move from (1, 1) to (0, 1)
Call API move from (0, 1) to (0, 2)
call clean API
Call API move from (0, 2) to (0, 1)
Call API move from (0, 1) to (0, 0)