Дана координатная плоскость.В первой строке задается размеренность координатной плоскости N*N и число запросов p. Далее идет p точек . Нужно проверить можно ли добраться из точки вида (0,w) до точки (v,0), где w,v какие-то точки, указанные при вводе.Передвигаться можно только по горизонтали и по вертикали(по диагонали нельзя). Пример:
Из точки с координатами (0,1), идем в (1,1) дальше в (1,2),потом в (2,2).
Ввод:
3 4
0 1
1 2
1 1
2 2
Вывод:
Yes
Объясните пожалуйста,как по координатам находить связь,т.е. из координаты с видом (0,w) переходить например в (1,k),потом в (2,z) и т.д.
longclaps, а ещё не понятно, зачем считать (p + v + w) % 2. Первое условие кажется самодостаточным, по крайней мере мне чет не приходит в голову кейс, который только по первому условию показал бы не правильный результат.
JaxxDexx, хрень какая-то.
Смотри, пусть v >= 0 <= w. Можно построить путь уголком, (v, 0) -> (0, 0) -> (0, w). А теперь просто повернём вторую часть пути, (v, 0) -> (0, 0) -> (-w, 0), как-будто повернули минутную стрелку часов, а часовую не тронули. Совокупная длина стрелок v + w как была, так и осталась. Разве не очевидно?
longclaps, наверное я не так поставил вопрос, задача по сути схожа с задачей "лабиринт",и переход осуществляется по координатной прямой x,но только когда координаты предыдущей точки равны (x-1,y), а последующей (x,y),т.е. точки должны быть на одном уровне y. Вот я и не понимаю как переходить из x-1 в x,поскольку есть 2 случая: а)когда несколько точек расположены на одинаковой координате x,но на разных y.И не понятно как их обходить и находить нужную,чтобы перейти на следующий уровень x+1.б)Когда есть несколько точек из которых можно перейти в x+1,но не каждая из таких точек дойдет до последнего x-нтого.
longclaps, очевидно, только причем здесь это?
Смотри, p = 7, v = -2, w = 5. Логично что из (-2, 0) -> (0, 5) нужно минимум 7 шагов. Т. е. у тебя пройдет условие p >= abs(v) + abs(w ). Но при этом not (p + v + w) % 2] не пройдет.
Правильно было бы написать:
print(('No', 'Yes')[p >= abs(v) + abs(w) and not (p - abs(v) - abs(w)) % 2])
longclaps, забыли про v,w . Фиолетовые и белые квадратики это положение точек на координатной прямой.,то бишь p -запросов. Фиолетовыми квадратиками обозначен маршрут с первого левого столбца. Нужно узнать,есть ли путь из первого левого столбца до последнего столбца.(на 1-нет,на 2-м есть). Вот у меня и возникает вопрос,как переходить из точек первого столбца к точкам последующих столбцов ?
longclaps, допустим,что-то вроде этого получилось, но как алгоритм дейкстры определит существование маршрута ? И словарь нужно преобразовывать в двумерный массив ? Разумеется я еще не вызывал функцию от дейкстры.
d = {}
first=list(map(int,input().split()))
n,k=first[0],first[1]
for i in range(n):
point=list(map(int,input().split()))
x=point[0]
y=point[1]
d[x,y] = [(x-1,y), (x+1, y), (x, y-1), (x, y+1)]
print(d)
def Dijkstra(N, S, matrix):
valid = [True]*N
weight = [1000000]*N
weight[S] = 0
for i in range(N):
min_weight = 1000001
ID_min_weight = -1
for i in range(len(weight)):
if valid[i] and weight[i] < min_weight:
min_weight = weight[i]
ID_min_weight = i
for i in range(N):
if weight[ID_min_weight] + matrix[ID_min_weight][i] < weight[i]:
weight[i] = weight[ID_min_weight] + matrix[ID_min_weight][i]
valid[ID_min_weight] = False
return weight
longclaps, coursera.cs.princeton.edu/algs4/assignments/percol... ,на питоне. Я думал методом UnionFind сделать,но там возникает проблема,поэтому и не знаю с чего начать,мыслей много а на деле ничего. Задача только от пункта перколяция до пункта модель включительно.
Rushpil, вот тебе демка к твоей задаче, думай дальше )
from random import shuffle
n, m = 20, 250 # размер поля, количество дыр
row = [0] * m + [1] * (n * n - m)
shuffle(row)
field = [row[i:i + n] for i in range(0, n * n, n)]
def show():
for r in field:
print('[', *[(' ', '██', '░░')[cell] for cell in r], ']', sep='')
print()
show()
# BFS https://ru.wikipedia.org/wiki/Поиск_в_ширину
row, nxt = field[0], []
for x, cell in enumerate(row):
if not cell:
nxt.append((0, x))
row[x] = 2
while nxt:
cur, nxt = nxt, []
for y, x in cur:
for y1, x1 in (y, x - 1), (y, x + 1), (y - 1, x), (y + 1, x):
if 0 <= y1 < n > x1 >= 0 == field[y1][x1]:
field[y1][x1] = 2
nxt.append((y1, x1))
show()
на 2-м изображении показан результат,на 1-м неверный результат. Т.е. Нужно попасть из начала в конец.