# 算法惡補日記——BFS算法（迷宮大逃亡writeup） -开发者知识库

### BFS算法框架

emmm自己算法的底子真的不咋樣。

T=2時：
2
3
1 1
1 3
OXO
OOO
XXX

3
1 2
3 3
XOX
OOX
XXO

Hint:

key值：CTF{xxxx}

BFS() //通常用隊列實現
{

Q =起點S;
while(Q非空)
{

if(U == 目標狀態 && U在矩陣內) {…}

}

``# coding=utf-8import threadingimport timeimport base64def openfile():    result = ""    f = open("ini.txt", "r")    i=int(f.readline().strip())    while (i != 0):        line=None        while not line:            line = f.readline().strip()        scale = int(line)        start = []        for x in f.readline().strip().split():            start.append(int(x)-1)        end = []        for x in f.readline().strip().split():            end.append(int(x)-1)        migong = []        for _ in range(scale):            migong.append(f.readline().strip())        r=pyqueue(len(migong[0]), start, end, migong)        result =str(r.run())        i = i - 1        #print result    print result    flag=""    for i in range(0,len(result),8):        c = result[i:i 8]        flag =chr(int(c,2))    print base64.b64decode(flag)class pyqueue:    def __init__(self, _len, _start, _end, _migong):        self.len = _len #地圖尺寸        self.start = _start #起點        self.end = _end #終點點 格式 [x,y]        self.migong = _migong #地圖        self.queue = [self.start] #初始的地方        self.steptrace = [] #走過的地方        self.sucess = 0   #判斷找到了終點    def Iqueue(self, location):        self.queue.append(location)        self.steptrace.append(location)    def Oqueue(self):        temp = self.queue[0]        del (self.queue[0])        return temp    def Void(self, location):        try:            if location in self.steptrace or self.migong[location[0]][location[1]] == "X":                return            else:                if location == self.end:                    self.sucess=1                    return                self.steptrace.append(location)                self.Iqueue(location)                return        except:            print "error"            print location    def empty(self):        try:            self.queue[0]            return True        except IndexError:            return False    def addx(self, x):        x  = 1        if x >= self.len: return x - 1        return x    def subx(self, x):        x -= 1        if x < 0: return x   1        return x    def run(self):        return str(self.zoumigong())    def zoumigong(self):        while self.empty():            location = self.Oqueue()            #print location            self.Void([self.addx(location[0]),location[1]])            self.Void([self.subx(location[0]), location[1]])            self.Void([location[0],self.addx(location[1])])            self.Void([location[0], self.subx(location[1])])            # 上下左右各試探一下            if self.sucess==1:                return 1        return 0# localtion=[x,y]# migong[location[0],local[1]]if __name__ == '__main__':    openfile()``

0条回复