SHARE
TWEET

tink

a guest May 19th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Graph(object):
  2.  
  3.     def __init__(self, graph_dict=None):
  4.         """ initializes a graph object
  5.            If no dictionary or None is given,
  6.            an empty dictionary will be used
  7.        """
  8.         if graph_dict == None:
  9.             graph_dict = {}
  10.         self.__graph_dict = graph_dict
  11.  
  12.     def vertices(self):
  13.         """ returns the vertices of a graph """
  14.         return list(self.__graph_dict.keys())
  15.  
  16.     def edges(self):
  17.         """ returns the edges of a graph """
  18.         return self.__generate_edges()
  19.  
  20.     def add_vertex(self, vertex):
  21.         """ If the vertex "vertex" is not in
  22.            self.__graph_dict, a key "vertex" with an empty
  23.            list as a value is added to the dictionary.
  24.            Otherwise nothing has to be done.
  25.        """
  26.         if vertex not in self.__graph_dict:
  27.             self.__graph_dict[vertex] = []
  28.  
  29.     def add_edge(self, edge):
  30.         """ assumes that edge is of type set, tuple or list;
  31.            between two vertices can be multiple edges!
  32.        """
  33.         edge = set(edge)
  34.         (vertex1, vertex2) = tuple(edge)
  35.         if vertex1 in self.__graph_dict:
  36.             self.__graph_dict[vertex1].append(vertex2)
  37.         else:
  38.             self.__graph_dict[vertex1] = [vertex2]
  39.  
  40.     def __generate_edges(self):
  41.         """ A static method generating the edges of the
  42.            graph "graph". Edges are represented as sets
  43.            with one (a loop back to the vertex) or two
  44.            vertices
  45.        """
  46.         edges = []
  47.         for vertex in self.__graph_dict:
  48.             for neighbour in self.__graph_dict[vertex]:
  49.                 if {neighbour, vertex} not in edges:
  50.                     edges.append({vertex, neighbour})
  51.         return edges
  52.  
  53.     def __str__(self):
  54.         res = "vertices: "
  55.         for k in self.__graph_dict:
  56.             res += str(k) + " "
  57.         res += "\nedges: "
  58.         for edge in self.__generate_edges():
  59.             res += str(edge) + " "
  60.         return res
  61.  
  62.     def find_all_paths(self, start_vertex, end_vertex, path=[]):
  63.         """ find all paths from start_vertex to
  64.            end_vertex in graph """
  65.         graph = self.__graph_dict
  66.         path = path + [start_vertex]
  67.         if start_vertex == end_vertex:
  68.             return [path]
  69.         if start_vertex not in graph:
  70.             return []
  71.         paths = []
  72.         for vertex in graph[start_vertex]:
  73.             if vertex not in path:
  74.                 extended_paths = self.find_all_paths(vertex,
  75.                                                      end_vertex,
  76.                                                      path)
  77.                 for p in extended_paths:
  78.                     paths.append(p)
  79.         return paths
  80.  
  81. n, m = map(int, input().split())
  82.  
  83. d = {}
  84. q = {}
  85. data = []
  86. string = ""
  87. for i in range(n):
  88.     s = str(input())
  89.     string += s
  90.     if i > 0:
  91.         for j in range(m - 1):
  92.             d[(i-1) * m + j] = [i * m + j, (i - 1) * m + j + 1]
  93.  
  94.         d[(i - 1) * m + (m - 1)] = [i * m + (m - 1)]
  95.  
  96. for i in range(m - 1):
  97.     d[m * (n - 1) + i] = [m * (n - 1) + i + 1]
  98.  
  99. graph = Graph(d)
  100. path = graph.find_all_paths(0, n * m - 1)
  101.  
  102. for i in path:
  103.     s = ''
  104.     for j in i:
  105.         s += string[j]
  106.  
  107.     bisect.insort(data, s)
  108. l = int(input())
  109. print(data[l - 1])
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top