在stackoverflow上看到一个有趣的问题：给定一张图片，如何表示并解决图片上的迷宫。
自己也写了一下，稍微用qt做了个界面。其实并没有用到什么很难的算法，只是一个简单的BFS。
当然迷宫上会有一个入口和出口，首先需要自己对图片做下预处理，把入口和出口封住，否则最后算出的最短路径将是从迷宫外面的空白区域绕过去的。另外程序运行之后还要用鼠标确定起点和终点，剩下就是从起点开始进行BFS，直到到达终点。另外需要注意的是边界和路径的区分，这个是通过计算像素点的灰度值，将灰度值超过一定限度的作为边界，低于的作为可以通过的区域。
[mw_shl_code=python,true] import sys import os from PyQt4.QtGui import * from PyQt4.QtCore import * from collections import deque class State: def __init__(self, x, y, pre=None): self.x = x self.y = y self.pre = pre def __str__(self): return "(%d, %d)" % (self.x, self.y) class MazeLabel(QLabel): def __init__(self, pixmap, path, parent=None): QLabel.__init__(self, parent) self.setPixmap(pixmap) self.path = path self.p1 = None self.p2 = None def isWhite(self, c): if abs(qGray(c) - qGray(qRgb(255, 255, 255))) < 30: return True else: return False def solve(self, img): q = deque() q.append(State(self.p1.x(), self.p1.y())) img.setPixel(self.p1.x(), self.p1.y(), qRgb(0, 0, 0)) print len(q) #cnt = 100 while len(q) > 0: s = q.popleft() #print s if s.x == self.p2.x() and s.y == self.p2.y(): return s for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nx, ny = s.x + dx, s.y + dy if nx >= 0 and nx < img.width() and ny >= 0 and ny < img.height() and self.isWhite(img.pixel(nx, ny)): q.append(State(nx, ny, s)) img.setPixel(nx, ny, qRgb(0, 0, 0)) #cnt = cnt - 1 print "no solution!" def mousePressEvent(self, ev): if self.p1 == None: self.p1 = ev.pos() else: self.p2 = ev.pos() print self.p1 print self.p2 image = self.pixmap().toImage() sol = self.solve(image) image = self.pixmap().toImage() it = sol while it != None: image.setPixel(it.x, it.y, qRgb(255, 0, 0)) it = it.pre self.setPixmap(QPixmap.fromImage(image)) self.update() fileName, fileExt = os.path.splitext(self.path) newFileName = fileName + "_solved" + fileExt self.pixmap().save(newFileName) if __name__ == "__main__": app = QApplication(sys.argv) scrollArea = QScrollArea() pixmap = QPixmap(sys.argv[1]) imageLabel = MazeLabel(pixmap, sys.argv[1]) scrollArea.setWidget(imageLabel) scrollArea.show() app.exec_() [/mw_shl_code]下面是一个迷宫的例子，非常复杂，入口在左上角，出口在右下角 
不过用程序，很容易能得出啊答案，下面是程序给出的解 
