[OJ]水位线问题，1.采用回溯法（深度优先遍历求解）2.采用广度优先遍历求解

1.深度优先遍历

'''
使用回溯法,深度优先遍历

利用栈先进后出的特点,在加水控制水量失败时,
回到最近一次可对水进行加水与否的位置

1.对于给定水量k,是否在[l,r]之间，
是:是否加水(加水y,用掉x,是否在[l,r]之间)
    (不加水y,用掉x,是否在[l,r]之间)
    先尝试加水，如果不满足条件，则回溯到之前位置
否:报错
'''classSStack(object):def__init__(self):# 初始化栈为空列表
        self.items =[]defis_empty(self):# 判断栈是否为空，返回布尔值return self.items ==[]defpeek(self):# 返回栈顶元素return self.items[len(self.items)-1]defsize(self):# 返回栈的大小returnlen(self.items)defpush(self, item):# 把新的元素堆进栈里面（入栈）
        self.items.append(item)defpop(self):# 把栈顶元素丢出去（出栈）return self.items.pop()defmain():# code here
    k,l,r,t,x,y=map(int,input().split(" "))
    ControlWaterAmount(k,l,r,t,x,y)defControlWaterAmount(k,l,r,t,x,y):
    dirs=[0,y]assert l<=k<=r
    #创建栈
    st=SStack()#标记当前日期的水量  k#入口和方向0、时间t的序对入栈
    st.push((k,0,t))whilenot st.is_empty():#走不通时回退#取栈顶及检查方向
        pos,nxt,t=st.pop()#依次检查未检查的方向，算出下一方向for i inrange(nxt,2):if l<=pos<=r:#当前时刻的偏移量为y(是否加水) 
                nextpos=pos+dirs[i]if nextpos>r:break#到达程序出口if l<=pos<=r and t==0:print('Yes')#遇到未探索的新方向if   l<=pos<=r :#标记当前时间 t#原位置、下一方向、时间t 入栈
                st.push((pos,i+1,t))#标记当前日期的水量 nextpos
                nextpos=nextpos-x            
                #新位置入栈
                st.push((nextpos,0,t-1))#退出内层循环，下次迭代将以新栈顶作为当前位置继续breakprint('No')if __name__ =='__main__':
    main();

提交测评结果：

原因分析：
当输入的时间t足够大时，会维持一个占内存极大的栈，栈中保存 t到1天的数据，造成超内存。

2.采用广度优先遍历

'''
以队列存储可以探索的位置。利用队列先进先出的特点，
实现在每个分支上同时进行搜索路径，直到找到出口。
广度优先遍历
'''classSQueue(object):"""实现一个队列"""def__init__(self):
        self.__list =[]defenqueue(self, elem):"""入队"""
        self.__list.append(elem)defdequeue(self):"""出队"""return self.__list.pop(0)defis_empty(self):returnnot self.__list

    defsize(self):"""队列的大小"""returnlen(self.__list)defControlWaterAmount_queue(k,l,r,t,x,y):
    dirs=[0,y]
    path=[]#存水量的变化#path.append(k)
    qu=SQueue()#标记当前日期的水量  k#开始水量、开始时间入队
    qu.enqueue((k,t))whilenot qu.is_empty():#当队列中还有候选水量时
        pos,t=qu.dequeue()#取出下一水量和时间for i inrange(2):#检查每种水量的情况if l<=pos<=r:
                nextpos=pos+dirs[i]if nextpos>r:continueif l<=pos<=r and t==0:#到达程序入口#path.append(pos)print('Yes')if l<=pos<=r:#找到新的探索方向#标记当前日期的水量 nextpos
                nextpos=nextpos-x
                qu.enqueue((nextpos,t-1))#新水量入队print('No')defmain():# code here
    k,l,r,t,x,y=map(int,input().split(" "))#ControlWaterAmount(k,l,r,t,x,y)
    ControlWaterAmount_queue(k,l,r,t,x,y)if __name__ =='__main__':
    main();

原因分析：当输入的时间t足够大时，会出现2^t次情况，每种情况都需要进行判断，会消耗大量的时间，直接导致超时

参考内容