маленькое открытие цикла в плоском графике
Прежде всего,
for (BigInteger number : input.nextLine().split(" "))
не будет работать, потому что .split() возвращает объект типа String[], и вы не можете напрямую трактовать String как BigInteger. ].
Кроме того, вы удваиваете свои циклы for. Та строка, которую я скопировал выше, , если работает так, как вы хотели, будет перебирать все числа на вашем входе. Так что нет необходимости в этом внутреннем цикле for. На самом деле, он даже не скомпилируется, поскольку BigInteger не имеет метода .length().
Но вы на правильном пути. То, что вы можете сделать, это токенизировать ввод, как вы уже делаете, и поместить каждый элемент в стек как есть. Потому что нет необходимости помещать их в стек как BigInteger. У вас может быть Stack<String>, а затем конвертировать их в BigInteger, когда вы вытаскиваете их обратно, чтобы выполнить сложение. Или, в качестве альтернативы, конвертируйте их в BigInteger, помещая каждый в стек.
3 ответа
Моим первым побуждением было использовать метод, аналогичный стене после решателя лабиринта . По сути, следуйте за ребрами и всегда вынимайте крайнее правое ребро из вершины. Любые циклы, с которыми вы столкнетесь при использовании этого метода, будут границами лица. Вам нужно будет отслеживать, какие края вы прошли в каком направлении. Пройдя край в обоих направлениях, вы определили грани, которые оно разделяет. После того, как все ребра пройдены в обоих направлениях, вы определите все грани по их границам.
A simple way to do this is to simply go out and enumerate each face. The principle is simple:
- We maintain 'α-visited' and 'β-visited' flags for each edge, and a pair of doubly-linked lists of unvisited edges for each such flag. The 'α' and 'β' division should correspond to a partition of the plane on the line corresponding to the edge in question; which side is α and which side is β is arbitrary.
- For each vertex V:
- For each adjacent pair of edges E = (V_1, V), E'=(V_2, V) (ie, sort by angle, take adjacent pairs, as well as first+last):
- Determine which side S of E (S=α or β) V_2 lies on.
- Walk the tile, starting at V, using side S of E, as described below:
Walking the tile is performed by:
- Let V = V_init
- Loop:
- V_next = the vertex of E that is not V
- E' = The adjacent edge to E from V_next that is on the current side of E
- S' = The side of E' that contains V
- If V_next = V, we have found a loop; record all the edges we passed by on the way, and mark those edge-pairs as visited.
- If E' = E (there is only one edge), then we have hit a dead end; abort this walk
- Otherwise, let V = V_next, E = E', S = S' and continue.
I hope this made sense; it perhaps needs some diagrams to explain...
«Пересекающийся край», как вы его называете, обычно известен как аккорд . Таким образом, ваша задача - найти все бесхордовые циклы.
Эта статья выглядит так, как будто она может помочь.