fork download
copy 
  1. # your code goes hereimport math
  2. from collections import deque
  3. from heapq import heapify,heappop,heappush
  4. def find(u, par):
  5.  
  6.     if par[u] != u:
  7.         par[u] = find(par[u], par)
  8.     return par[u]
  9.  
  10. def union(u, v, par, size):
  11.     u_root = find(u, par)
  12.     v_root = find(v, par)
  13.  
  14.     if u_root == v_root:
  15.         return 
  16.  
  17.  
  18.     if size[u_root] < size[v_root]:
  19.         par[u_root] = v_root
  20.         size[v_root] += size[u_root]
  21.     else:
  22.         par[v_root] = u_root
  23.         size[u_root] += size[v_root]
  24.  
  25. def ip():
  26.     return map(int,input().split())
  27.  
  28.  
  29.  
  30.  
  31. T=1
  32. # T=int(input())
  33. for __ in range(T):
  34.     n=int(input())
  35.     g=[]
  36.     for _ in range(n):
  37.         s=str(input())
  38.         g.append(s)
  39.  
  40.     dist=[[float('inf') for _ in range(n)] for _ in range(n)]
  41.     par=[[(-1,-1) for _ in range(n)] for _ in range(n)]
  42.  
  43.     dist[0][0]=0
  44.     direc=[(1,0),(0,1)]
  45.     q=deque()
  46.     q.append((0,0,0))
  47.     while q:
  48.         ln=len(q)
  49.         mn=26
  50.         lst=[]
  51.         for _ in range(ln):
  52.             d,u,v=q.popleft()
  53.             if u==n-1 and v==n-1:
  54.                 break
  55.             for t1,t2 in direc:
  56.                 x,y=u+t1,v+t2
  57.                 if 0<=x<n and 0<=y<n:
  58.                     m=ord(g[x][y])-ord('a')
  59.                     if m<mn:
  60.                         mn=m
  61.                         lst=[(x,y,u,v)]
  62.                     elif m==mn:
  63.                         lst.append((x,y,u,v))
  64.         for i in lst:
  65.             u,v,x,y=i
  66.             if d+1<dist[u][v]:
  67.                 dist[u][v]=d+1
  68.                 par[u][v]=(x,y)
  69.                 q.append((d+1,u,v))
  70.  
  71.     path=[]
  72.     x=n-1
  73.     y=n-1
  74.  
  75.     while par[x][y]!=(-1,-1):
  76.         path.append(g[x][y])
  77.         px,py=par[x][y]
  78.         x,y=px,py
  79.     path.append(g[0][0])
  80.     print("".join(path[::-1]))
  81.  
  82.  
  83.  
  84.  
Success #stdin #stdout 0.09s 14124KB
comments (?)
stdin
copy 
4
AACA
BABC
ABDA
AACA
stdout
copy 
AAABACA
https://ideone.com/j8fu7d
language:
Python 3 (python  3.12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!