頭一次發帖，有點小緊張
網上看到這樣一道題：
迷宮大小為NxN,N的大小未知.
我們在迷宮里的任意一點開始走,此點的位置未知,因些,記它的坐標為(0,0).
迷宮只有一個出口.
從起始處可以到達迷宮的任意一點,且只有一條路.
在起點處,我們的方向是向上.我們可以發送向左轉"L",向右轉"R",向前走"F"三種指令.一次最多可以發16條指令.當指令執行之后,回傳當前的坐標,坐標是相對于起點的,形式為(x,y).
坐標系如下:
+→ x
↓
y
如果到達出口,回傳"OUT".
我們最多可以發送5000個指令序列.
測驗時地圖的大小在5~20之間.
計分方式:
對于NxN的迷宮,如果走出需要M條指令.而你的程式發送了S個指令序列,C條指令.那你的得分為: N*M/(10*S+C)
地圖為如下形式(R為起點):
+-+.+-+-+-+
|...| |
+.+-+-+-+ +
|... | |
+-+.+-+ +-+
|R.. | |
+ +-+-+-+ +
| | |
+ + + +-+ +
| | | |
+-+-+-+-+-+
我很菜，只會列舉和遞回，個人解法如下：
ferry=[[]]
i=0
way_dict={}
final_way=[]
result_ways_dict={}
def find_way(x,y,way_dict,result_ways_dict):
global i,j
i+=1
j=1
if x-1>=0 and x<N and j>=0 and j<N and ferry[x-1][j]==" " and ((x-1,y) not in way_dict[(i,j)] ) and ((i,j) not in result_ways_dict.keys()):
way_dict[(i,j)].append((x-1,y))
return find_way(x-1,y,way_dict,result_ways_dict)
if x+1<N and x>=0 and j>=0 and j<N and ferry[x+1][j]==" " and ((x+1,y) not in way_dict[(i,j)]) and ((i,j) not in result_ways_dict.keys()):
j+=1
way_dict[(i, j)].append((x+1,y))
return find_way(x+ 1, y,way_dict,result_ways_dict)
if x>=0 and x<N and j+1<N and j>=0 and ferry[x][j+1]==" " and ((x,y+1) not in way_dict[(i,j)]) and ((i,j) not in result_ways_dict.keys()):
j+=1
way_dict[(i, j)].append((x,j+1))
return find_way(x , y+1,way_dict,result_ways_dict)
if x>=0 and x<N and j-1>=0 and j<N and ferry[x][j-1]==" " and ((x,y-1) not in way_dict[(i,j)]) and ((i,j) not in result_ways_dict.keys()):
j += 1
way_dict[(i, j)].append((x, j - 1))
return find_way(x, y - 1,way_dict,result_ways_dict)
if ((x==0 or x==N) and 0<=y<N) or (0<=x<N and (y==0 or y==N)) and (dict[(i,j)] not in result_ways):
if ferry[x][y]==" ":
result_ways_dict[(i,j)].append(way_dict[(i,j)])
return
return
def handle(address):
for l in range(1,len(address)):
if address[l][0]-address[l-1][0]==1:
final_way.append("right")
elif address[l][0] - address[l - 1][0] == -1:
final_way.append("left")
elif address[l][1]-address[l-1][1]==1:
final_way.append("up")
else:
final_way.append("down")
return final_way
def main():
lambda_list=[]
for i in range(N**2):
find_way(x,y,way_dict,result_ways_dict) #(x,y)為起點坐標
for j in result_ways_dict.values():
lambda_list.append(j)
min_way=min(lambda_list)
final_way=handle(min_way)
print(final_way)
if __name__=="__main__":
main()
如果程序結果正確，應該能拿到最高分吧
還望大佬斧正
uj5u.com熱心網友回復：
不錯不錯， 發個博文唄。轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/26564.html