список смежности ориентированного графа
Дана олимпиадная задача по информатике:
Задача A. Город перекрёстков Вы разрабатываете навигатор для одного города. Этот город разбит улицами на квадратные кварталы, причём движение по любому из отрезков улицы в пределах каждого квартала строго одностороннее. С каждого перекрёстка можно выехать только в разрешённых знаками направлениях. Требуется по прилагаемой карте города с указанными на ней разрешёнными направлениями перемещения проложить самый короткий маршрут из точки AA в точку BB.
Формат входных данных
На вход подаётся карта перекрёстков города. В первой строке содержатся два числа NN — число кварталов с севера на юг и MM — число кварталов с запада на восток (1 ≤ n ≤ 50). Точка AA самая северо-западная, точка BB самая юго-восточная. Далее в 2*N+12∗N+1 строках содержится описание разрешённых направлений движения. Улицы города запад-восток описаны в нечётных строках. В каждой такой строке содержится по MM символов без пробела, указывающих разрешённое движение на соответствующем участке. В чётных строках содержится описание улиц север-юг. В этих строках содержится по M+1M+1 символов, указывающих возможное движение по отрезкам улиц север-юг. Движение на север, юг, запад, восток обозначается буквами n, s, w, e соответственно.
Формат выходных данных
В первую строку вывести число отрезков улиц в самом коротком маршруте из точки AA в точку BB. Во вторую строку нужно выдать описание этого маршрута в виде последовательности символов n, s, w, e без пробелов. Если кратчайших маршрутов несколько, выдать самый первый среди них по алфавитному порядку. Гарантируется, что из точки AA можно попасть в точку BB.
Пояснение к первому примеру
Sample Input 1:
4 5
weeee
snssss
wewww
snsnns
weeew
snnsns
wwwew
ssssns
eeeew
Sample Output 1:
29
sssseeeennnwwseswwnnneeeessss
Sample Input 2:
2 2
ee
sss
ee
sss
ee
Sample Output 2:
4
eess
Первое, что пришло мне в голову, - это создать списки смежности ориентированного графа:
n, m = map(int, input().split())
west_east = []
north_south = []
for i in range(1, 2 * n + 2):
if i % 2 != 0:
west_east.append(input())
else:
north_south.append(input())
graphs = []
for i in range((n+1)*(m+1)):
graphs.append([])
if west_east[i % (n + 1)][(i - 1) % m] == 'w' and i - 1 >= 0:
graphs[i].append(i - 1)
elif i % (m + 1) != m:
graphs[i].append(i + 1)
if north_south[(i - 1) % n][i % (m + 1)] == 'n' and i - (m + 1) >= 0:
graphs[i].append(i - (m + 1))
elif i + m + 1 < 9:
graphs[i].append(i + (m + 1))
print(west_east)
print(north_south)
print(graphs)
Однако мой код работает не совсем правильно. Он выдает, допустим, для нулевой вершины 1 и 6, когда он должен выдавать 6, так как путь из 0 ведет только туда. Помогите разобраться, я запутался(((
Ответы (2 шт):
n, m = map(int, input().split())
west_east = []
north_south = []
for i in range(1, 2 * n + 2):
if i % 2 != 0:
west_east.append(input())
else:
north_south.append(input())
graphs = [[] for i in range((n + 1) * (m + 1))]
for i in range((n + 1) * (m + 1)):
if west_east[i % (n + 1)][(i - 1) % m] == 'w' and (i - 1) % m + 1 == i:
if i - 1 not in graphs[i]:
graphs[i].append(i - 1)
elif west_east[i % (n + 1)][(i - 1) % m] == 'w' and (i - 1) % m - 1 == i:
if i - 1 not in graphs[i]:
graphs[i + 1].append(i)
elif west_east[i % (n + 1)][(i - 1) % m] == 'e' and (i - 1) % m - 1 == i:
if i + 1 not in graphs[i]:
graphs[i].append(i + 1)
elif west_east[i % (n + 1)][(i - 1) % m] == 'e' and (i - 1) % m + 1 == i:
if i + 1 not in graphs[i - 1]:
graphs[i - 1].append(i)
if north_south[(i - 1) % n][i % (m + 1)] == 'n' and i - (m + 1) >= 0:
graphs[i].append(i - (m + 1))
elif i + m + 1 < 9:
graphs[i].append(i + (m + 1))
print(west_east)
print(north_south)
print(graphs)
Вот что у меня получилось и это вроде-бы работает
n, m = [int(i) for i in str(input()).split()]
points = []
for i in range(n + 1):
k = []
for j in range(m + 1):
k.append(str(i) + '_' + str(j))
points.append(k)
k = []
for i in points:
for j in i:
k.append(j)
napr = []
for i in range(n):
napr.append([str(input()) + '-', str(input())])
napr.append([str(input())])
pointsnap = points.copy()
for i in range(len(pointsnap)):
for j in range(len(pointsnap[i])):
pointsnap[i][j] = []
for i in range(len(napr)):
for j in range(len(napr[i][-1])):
if i == 0 and j == 0:
if napr[i][0][j] == 'e':
pointsnap[i][j].append('e')
if napr[i][-1][j] == 's':
pointsnap[i][j].append('s')
elif i == 0 and j != 0 and j < len(napr[0][-1]) - 1:
if j - 1 >= 0:
if napr[i][0][j - 1] == 'w':
pointsnap[i][j].append('w')
if napr[i][0][j] == 'e':
pointsnap[i][j].append('e')
if napr[i][-1][j] == 's':
pointsnap[i][j].append('s')
elif i == 0 and j == len(napr[0][0]) - 1:
if j - 1 >= 0:
if napr[i][0][j - 1] == 'w':
pointsnap[i][j].append('w')
if napr[i][-1][j] == 's':
pointsnap[i][j].append('s')
elif i != 0 and i < len(napr) - 1 and j == 0:
if napr[i - 1][-1][j] == 'n':
pointsnap[i][j].append('n')
if napr[i][-1][j] == 's':
pointsnap[i][j].append('s')
if napr[i][0][j] == 'e':
pointsnap[i][j].append('e')
elif i == len(napr) - 1 and j == 0:
if (i - 1) >= 0:
if napr[i - 1][-1][j] == 'n':
pointsnap[i][j].append('n')
if napr[i][0][j] == 'e':
pointsnap[i][j].append('e')
elif i != 0 and i < len(napr) - 1 and j != 0 and j < len(napr[0][-1]) - 1:
if napr[i][0][j] == 'e':
pointsnap[i][j].append('e')
if (i - 1) >= 0:
if napr[i - 1][-1][j] == 'n':
pointsnap[i][j].append('n')
if napr[i][-1][j] == 's':
pointsnap[i][j].append('s')
if (j - 1) >= 0:
if napr[i][0][j - 1] == 'w':
pointsnap[i][j].append('w')
elif i == (len(napr) - 1) and j != 0:
if napr[i][0][j] == 'e':
pointsnap[i][j].append('e')
if (j - 1) >= 0:
if napr[i][0][j - 1] == 'w':
pointsnap[i][j].append('w')
if (i - 1) >= 0:
if napr[i - 1][-1][j] == 'n':
pointsnap[i][j].append('n')
elif i != 0 and j == (len(napr[0][0]) - 1):
if napr[i][-1][j] == 's':
pointsnap[i][j].append('s')
if (i - 1) >= 0:
if napr[i - 1][-1][j] == 'n':
pointsnap[i][j].append('n')
if (j - 1) >= 0:
if napr[i][-1][j - 1] == 'w':
pointsnap[i][j].append('w')
count = 0
for i in range(len(pointsnap)):
for j in range(len(pointsnap[i])):
pointsnap[i][j].append(str(count))
count += 1
con = dict()
for i in range(len(points)):
for j in range(len(points[i])):
d = []
for h in pointsnap[i][j]:
if h == 'e':
d.append(pointsnap[i][j + 1][-1])
elif h == 's':
d.append(pointsnap[i + 1][j][-1])
elif h == 'w':
d.append(pointsnap[i][j - 1][-1])
elif h == 'n':
d.append(pointsnap[i - 1][j][-1])
con[pointsnap[i][j][-1]] = d
def bfs(graph_to_search, start, end):
queue = [[start]]
visited = set()
while queue:
path = queue.pop(0)
vertex = path[-1]
if vertex == end:
return path
elif vertex not in visited:
for current_neighbour in graph_to_search.get(vertex, []):
new_path = list(path)
new_path.append(current_neighbour)
queue.append(new_path)
visited.add(vertex)
path = [int(i) for i in bfs(con, '0', str(count - 1))]
print(len(path) - 1)
path2 = []
count = 0
for i in range(len(pointsnap)):
for j in range(len(pointsnap[i])):
pointsnap[i][j] = count
count += 1
row = 0
column = 0
for i in path[1:]:
if i in pointsnap[row]:
if i < pointsnap[row][column]:
path2.append('w')
column -= 1
else:
path2.append('e')
column += 1
else:
if (row - 1) >= 0 and i in pointsnap[row - 1]:
path2.append('n')
row -= 1
else:
path2.append('s')
row += 1
print(''.join(path2))