当前位置：首页 > news >正文

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

news 2025/8/23 15:40:22

在这里插入图片描述
1.深度优先遍历

'''
使用回溯法,深度优先遍历利用栈先进后出的特点,在加水控制水量失败时,
回到最近一次可对水进行加水与否的位置1.对于给定水量k,是否在[l,r]之间，
是:是否加水(加水y,用掉x,是否在[l,r]之间)(不加水y,用掉x,是否在[l,r]之间)先尝试加水，如果不满足条件，则回溯到之前位置
否:报错
'''
class SStack(object):def __init__(self):		  # 初始化栈为空列表self.items = []def is_empty(self):		# 判断栈是否为空，返回布尔值return self.items == []def peek(self):		  # 返回栈顶元素return self.items[len(self.items) - 1]def size(self):		  # 返回栈的大小return len(self.items)def push(self, item):		# 把新的元素堆进栈里面（入栈）self.items.append(item)def pop(self):		   # 把栈顶元素丢出去（出栈）return self.items.pop()def main():# code herek,l,r,t,x,y=map(int,input().split(" "))ControlWaterAmount(k,l,r,t,x,y)def ControlWaterAmount(k,l,r,t,x,y):dirs=[0,y]assert l<=k<=r#创建栈st=SStack()#标记当前日期的水量  k#入口和方向0、时间t的序对入栈st.push((k,0,t))while not st.is_empty():#走不通时回退#取栈顶及检查方向pos,nxt,t=st.pop()#依次检查未检查的方向，算出下一方向for i in range(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))#标记当前日期的水量 nextposnextpos=nextpos-x            #新位置入栈st.push((nextpos,0,t-1))#退出内层循环，下次迭代将以新栈顶作为当前位置继续breakprint('No')if __name__ == '__main__':main();

提交测评结果：
在这里插入图片描述
原因分析：
当输入的时间t足够大时，会维持一个占内存极大的栈，栈中保存 t到1天的数据，造成超内存。

2.采用广度优先遍历

'''
以队列存储可以探索的位置。利用队列先进先出的特点，
实现在每个分支上同时进行搜索路径，直到找到出口。
广度优先遍历
'''
class SQueue(object):"""实现一个队列"""def __init__(self):self.__list = []def enqueue(self, elem):"""入队"""self.__list.append(elem)def dequeue(self):"""出队"""return self.__list.pop(0)def is_empty(self):return not self.__listdef size(self):"""队列的大小"""return len(self.__list)def ControlWaterAmount_queue(k,l,r,t,x,y):dirs=[0,y]path=[] #存水量的变化#path.append(k)qu=SQueue()#标记当前日期的水量  k#开始水量、开始时间入队qu.enqueue((k,t))while not qu.is_empty():#当队列中还有候选水量时pos,t=qu.dequeue()#取出下一水量和时间for i in range(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:#找到新的探索方向#标记当前日期的水量 nextposnextpos=nextpos-xqu.enqueue((nextpos,t-1))#新水量入队print('No')def main():# code herek,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();