9/9練習

a981: 畫蛇添足

題目:詳見此

思路:用基本的遞迴寫，但是速度在測資大之後太慢了，還在想加速的方法。

            a,target=[int(i) for i in input().split()]
            list=[int(i) for i in input().split()]
            slist=sorted(list)
            def DFS(target,numlist,pathtotal=0,path='',count=0):
                if pathtotal == target:
                    print(path)
                    return
                if count==len(numlist) or pathtotal>target:
                    return
                now=pathtotal
                pathtotal+=numlist[count]
                DFS(target,numlist,pathtotal,path+str(numlist[count])+' ',count+1)
                DFS(target,numlist,now,path,count+1)
            DFS(target,slist)

a982: 迷宮問題#1

題目:詳見此

思路:DFS太慢了，改用BFS。思路是建立route，每次都抓出第一個來看，保證能同時擴散走迷宮，並建立memo保證不會重複亂走。

            n=int(input())
            maze=[]
            for i in range(n):
                maze.append(input().split())
            def shortpath(maze,count=0,end=[n-2,0,n-2],now=[1,0,1],visited=[]): #BFS 紀錄 ([x,y],步數)
                queue=[[now,count]]
                while len(queue)>0:
                    popthing= queue.pop(0)
                    x,y,distance=popthing[0][0],popthing[0][2],popthing[1]
                    if [x,y] in visited:
                        continue
                    visited.append([x,y])
                    if [x,0,y] == end:
                        print(distance+1)
                        return
                    if maze[x][0][y+1]=='.':
                        queue.append([[x,0,y+1],distance+1])
                    if maze[x+1][0][y]=='.':
                        queue.append([[x+1,0,y],distance+1])
                    if maze[x-1][0][y]=='.':
                        queue.append([[x-1,0,y],distance+1])
                    if maze[x][0][y-1]=='.':
                        queue.append([[x,0,y-1],distance+1])
                print('No solution!')
                return
            shortpath(maze)

b265: Q11286 - Conformity

題目:詳見此

思路:把課排序後轉成string，在用字典型態紀錄，滿足題目需求後輸出。

        while True:
            try:
                n=int(input())
                if n==0:
                    break
                classes=[]
                memo={}
                count=0 #幾門課
                popular=False #有沒有最受歡迎的課
                maxpop=0 #最受歡迎的課幾個人選
                pops=1  #有幾組最受歡迎的課
                for i in range(n):
                    a=sorted(input().split())
                    classes.append(''.join(a))
                for choose in classes:
                    if choose in memo:
                        memo[choose]+=1
                        if memo[choose]==maxpop:
                            pops+=1
                        if memo[choose]>maxpop:
                            maxpop=memo[choose]
                            pops=1
                        popular=True
                    else:
                        memo[choose]=1
                        count+=1
                if popular:
                    print(maxpop*pops)
                else:
                    print(count)
            except:break

arrow_circle_left home arrow_circle_right