所以最近我一直在解决很多图形问题,并使用Python来解决问题, 但是每当我用Python甚至C++解决与CordChf或HackerEarth有关的问题时,在每个问题的一些测试案例中,它给出了TLE,我确信我不会超过O(n)。请帮帮我
这样,CodeChef Question 1是基本的BFS,DFS问题,这是^ {A2},很多人告诉我,这是因为Python是一种缓慢的语言,但它对我来说没有意义,因为所有这些竞争性编程站点都认为与P/C++相比,Python代码的5X时间。 有趣的事实是,有许多python解决方案是针对同一个CodeChef Question 1的,我认为他们做了同样的事情,但没有得到TLE,例如,这些Some guy's Solution 1、Some guy's solution 2和Some guy's solution 3
如果您能告诉我这些家伙的解决方案和我的解决方案有什么区别,或者问题在我的代码中的具体位置(我在哪里花费额外的时间),那将是一个很大的帮助。
在这之后,我尝试用C++实现它,不幸的是,没有魔法发生,它也给了我太多的能量。{a7}如果您不想转到这些链接:
我的Python解决方案1:
from collections import defaultdict
from collections import deque
class Graph:
def __init__ (self):
self.graph = defaultdict(list)
self.ll=0
self.flag=0
self.visit={}
self.rp={}
def creategh(self,a,b):
try:
self.rp[(a,b)]+=1
except:
self.rp[(a,b)]=1
if(a!=b):
self.graph[a].append(b)
def bfs(self,n):
dq = deque([])
self.ll=0
dq.appendleft(n)
self.visit[n]=1
while(dq):
s = dq.pop()
self.ll+=1
for i in self.graph[s]:
try:
self.visit[i] +=1
except:
self.visit[i] = 1
dq.appendleft(i)
return self.ll
g = Graph()
n,m = map(int,input().split())
x=[]
a= list(map(int,input().split()))
x.append(a)
for i in range(len(a)-1):
if(a[i]==a[i+1]):
g.creategh((0,i),(0,i+1))
g.creategh((0,i+1),(0,i))
for i in range(1,n):
a= list(map(int,input().split()))
x.append(a)
for j in range(m):
try:
if(x[i][min(j+1,m-1)]==x[i][j]):
g.creategh((i,j),(i,min(j+1,m-1)))
g.creategh((i,min(j+1,m-1)),(i,j))
except:
do="nothing"
try:
if(x[max(0,i-1)][j]==x[i][j]):
g.creategh((max(i-1,0),j),(i,j))
g.creategh((i,j),(max(i-1,0),j))
except:
do="nothing"
mmx=-999999999999999
mnxm=9999999999999999999999999999999
for i in range(n):
for j in range(m):
try:
g.visit[i]+=1
except:
lol=g.bfs((i,j))
if(lol>mmx):
mmx=lol
mnxm=x[i][j]
elif(lol==mmx):
if(mnxm>x[i][j]):
mnxm=x[i][j]
print(mnxm,mmx)
目前没有回答
相关问题 更多 >
编程相关推荐