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

算法惡補日記——BFS算法(迷宮大逃亡writeup) -开发者知识库,第1张

BFS算法框架

聽打ACM的室友說,這是一個很基礎的算法
emmm自己算法的底子真的不咋樣。
真巧在實驗吧上遇到了一道題目。
根據題目的說明,編寫代碼達到題目的要求。即可得到flag,一般flag格式是ctf{},所以在編寫的代碼,最終結果可能需要轉碼操作

你掉進了一個連環迷宮, 這個連環迷宮總共有T個迷宮~
每個迷宮有如下信息:
迷宮大小n (表示這是n*n的迷宮)
迷宮入口坐標
迷宮出口坐標
迷宮地圖(由’X’, ‘O’組成的n行n列的迷宮,’X’表示障礙物, 即不可走,’O’表示可走的道路)

如果能走出這個迷宮那么你將得到一個1,否則你將得到一個0
這T個 0/1就是你走出這個連環迷宮的鑰匙

示例:
T=2時:
2
3
1 1
1 3
OXO
OOO
XXX

3
1 2
3 3
XOX
OOX
XXO

那么鑰匙為:10

Hint:

這T個迷宮在in.txt文件里,這個文件第一行就是T, 接下來就是T個迷宮的信息

key值:CTF{xxxx}

問了問室友這是咋做的,室友一笑,拋給了我一個模板

BFS() //通常用隊列實現
{
初始化隊列Q;
清除visited數組;
Q =起點S;
while(Q非空)
{
取隊首元素U;出隊;
if(U == 目標狀態 && U在矩陣內) {…}
所有與U相鄰且未被訪問的狀態入隊;
標記U為已訪問;
}

然后大致理解了一下,用python完成了這道題目

題目鏈接 迷宮大逃亡

# coding=utf-8
import threading
import time
import base64
def 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条回复