#!/usr/bin/env python
# -*- coding: utf-8 -*-
class clean:
    def __init__(self, points):
        self.result = []
        self.matrix = [[0 for i in range(5)] for j in range(5)]
        for pt in points:
            self.matrix[pt[0] - 1][pt[1] - 1] = 1
            
    def cleanRoom(self):
        visited = []
        matrix = self.matrix
        for i in range(5):
            for j in range(5):
                if matrix[i][j] == 1:
                    visited.append(i * 5 + j)
        for i in range(5):
            for j in range(5):
                if matrix[i][j] == 0:
                    step = []
                    startPoint = i * 5 + j
                    step.append((i,j))
                    visited.append(startPoint)
                    self.dfs(startPoint, step, visited)
                    visited.pop()
                    step.pop()
        newResult = self.resultHandle(self.result)
        return newResult
    def dfs(self, startPoint, step, visited):
        summ = len(visited)
        if summ == 25:
            self.result.append(step[:])
            return
        dx = [0,0,-1,1]
        dy = [1,-1,0,0]
        x = startPoint // 5
        y = startPoint % 5
        for i in range(4):
            ptX = x + dx[i]
            ptY = y + dy[i]
            k = 0
            if self.insideMatrix(ptX, ptY) and ptX * 5 + ptY not in visited:
                visited.append(ptX * 5 + ptY)
                k += 1
                step.append((ptX, ptY))
                if dx[i] != 0:
                    while self.insideMatrix(ptX + dx[i], ptY) and (ptX + dx[i]) * 5 + ptY not in visited:
                        visited.append((ptX + dx[i]) * 5 + ptY)
                        k += 1
                        ptX += dx[i]
                    startPoint = ptX *  5 + ptY
                    self.dfs(startPoint, step, visited)
                    step.pop()
                    while k > 0:
                        visited.pop()
                        k -= 1
                elif dy[i] != 0:
                    while self.insideMatrix(ptX, ptY + dy[i]) and ptX * 5 + ptY + dy[i] not in visited:
                        visited.append(ptX * 5 + ptY + dy[i])
                        k += 1
                        ptY += dy[i]
                    startPoint = ptX *  5 + ptY
                    self.dfs(startPoint, step, visited)
                    step.pop()
                    while k > 0:
                        visited.pop()
                        k -= 1
    def insideMatrix(self, ptX, ptY):
        if ptX >= 0 and ptX < 5 and ptY >= 0 and ptY < 5:
            return True
        return False
   
    def resultHandle(self, result):
        newResult = []
        for r in result:
            tempR = []
            for t in r:
                temp = (t[0] + 1, t[1] + 1)
                tempR.append(temp)
            newResult.append(tempR)  
        return newResult

#有些障碍方案是无解的，函数返回值会为空
#points 括号内为障碍的坐标， e.g. [1,1]代表x=1,y=1的障碍, 把[]内的数字替换即可, 若有新增加的点，则加上'[x, y],' 不要忘记半角逗号’,‘
#############################此处修改坐标！！！！！！！！！！
points = [[1,3],[1,4],[1,5],[5,1],[5,2]]
################################

cl = clean(points)
print(cl.cleanRoom())
#输出的结果为，每一步你需要点击的坐标，如（1，5）为x = 1， y = 5的位置

[此贴子已经被作者于2018-11-22 00:10编辑过]