摄影网站怎么做,物流网站建设 市场分析,ppt做杂志模板下载网站有哪些,wordpress是php模板吗1.深度优先遍历 使用回溯法,深度优先遍历利用栈先进后出的特点,在加水控制水量失败时,
回到最近一次可对水进行加水与否的位置1.对于给定水量k,是否在[l,r]之间#xff0c;
是:是否加水(加水y,用掉x,是否在[l,r]之间)(不加水y,用掉x,是否在[l,r]之间)先尝试加水#xff0c;如… 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,ymap(int,input().split( ))ControlWaterAmount(k,l,r,t,x,y)def ControlWaterAmount(k,l,r,t,x,y):dirs[0,y]assert lkr#创建栈stSStack()#标记当前日期的水量 k#入口和方向0、时间t的序对入栈st.push((k,0,t))while not st.is_empty():#走不通时回退#取栈顶及检查方向pos,nxt,tst.pop()#依次检查未检查的方向算出下一方向for i in range(nxt,2):if lposr:#当前时刻的偏移量为y(是否加水) nextposposdirs[i]if nextposr:break#到达程序出口if lposr and t0:print(Yes)#遇到未探索的新方向if lposr :#标记当前时间 t#原位置、下一方向、时间t 入栈st.push((pos,i1,t))#标记当前日期的水量 nextposnextposnextpos-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)quSQueue()#标记当前日期的水量 k#开始水量、开始时间入队qu.enqueue((k,t))while not qu.is_empty():#当队列中还有候选水量时pos,tqu.dequeue()#取出下一水量和时间for i in range(2):#检查每种水量的情况if lposr:nextposposdirs[i]if nextposr:continueif lposr and t0: #到达程序入口#path.append(pos)print(Yes)if lposr:#找到新的探索方向#标记当前日期的水量 nextposnextposnextpos-xqu.enqueue((nextpos,t-1))#新水量入队print(No)def main():# code herek,l,r,t,x,ymap(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次情况每种情况都需要进行判断会消耗大量的时间直接导致超时
参考内容
