행렬이 있고 각 셀에 부울 값이 있습니다. 부울 속성이 false 인 셀에서 시작하여 사이클을 결정해야하며이 사이클에는 부울 속성이 true로 설정된 셀만 포함되어야합니다 (시작 셀 제외). 또 다른 조건은주기의 두 연속 된 셀이 동일한 행 (또는 동일한 열)에 있어야하며주기의 세 개의 연속 셀이 같은 행 (또는 같은 열)에 있으면 안됩니다. 실제로 하나의 셀에서 다른 셀로 이동할 수 있습니다. 이웃이 될 필요는 없으며 같은 행이나 열에 있어야합니다. 감사합니다.행렬의 사이클을 결정하십시오.
업데이트 : 두 개의 인접한 셀 사이에 이동이 필요하지 않습니다. 각 단계마다 가능한 이동 수는 늘어 났지만 실제로는 일반적인 아이디어가 변경되지 않았습니다.
가장 쉬운 구현은 아마도 depth-first search입니다. 시작 셀에서 시작하여 가능한 모든 이동을 살펴 봅니다. 첫 번째 이동의 경우를 제외하고는 세 가지 가능한 이동이 있습니다. 가능한 각 이동에 대해 다시 시작 셀에 도달하거나 가능한 이동이 남아 있지 않을 때까지 동일한 반복을 수행합니다. 나중의 경우에는 한 번의 이동을 추적하여 남은 것이 있으면 다음 가능성을 시도하십시오.
이 방향이 다음 이동에 유효하지 않으므로 재귀 호출과 함께 마지막 이동 방향을 전달해야합니다. 셀을 여러 번 방문하는 것이 허용되지 않으면 방문한 셀을 추적해야하며 뒤로 추적 할 때 표시를 해제해야합니다. 셀을 여러 번 방문하는 것이 허용되면 사이클을 피하기 위해 이전에 방문했을 때 셀을 떠난 방향을 추적해야합니다.
심도 우선 검색 대신 breath-first search을 사용하면 많은 부분 솔루션을 유지하는 대신에 해결 방법이없는 긴 경로를 사용하지 않아도됩니다. A* search은 속도를 높이는 또 다른 옵션 일 수 있습니다.
사이드 노트 : 처음으로 셀을 방문 할 때 다른 동작을 직접 수행 할 수 있으므로 셀을 여러 번 방문 할 가치가없는 경우 일 수 있습니다. 예외는 처음으로 셀을 입력 할 때 허용되지 않는 이동을 수행하는 것이며 이지만 이러한 경로가 가능한지 확실하지 않습니다.
노드 당 한 비트를 추적하면됩니다. 열 이동 또는 행 이동. 따라서 노드 수를 두 배로 늘리고 이동 만 연결하는 등의 작업을 수행 할 수도 있습니다."여기에서 열 이동으로 표시되었습니다"라는 셀에서 동일한 행에 "여기에 행 이동으로 나타났습니다"라고 표시된 셀에서 순환 감지에 대해 일부 표준 그래프 알고리즘을 사용할 수 있습니다. – mcdowella
다니엘과 mcdowella 감사합니다. 알았어, 재귀를 구현하는 방법을 알아 내야 멈출 때를 알 수있다. -? – Cosmin
단일 비트가 실제로 충분합니까? 왼쪽과 오른쪽, 위쪽과 아래쪽을 각각 구분할 필요가 없습니다. 다른 생각은 가능한 움직임의 방향 그래프를 작성한 다음 시작 노드에서 시작 노드의 도달 가능성을 테스트하는 것이 었습니다. 그러나 들어오는 방향에서 가능한 움직임의 의존성 때문에 셀당 네 개의 노드가 필요합니다. 그리고 이것은 아마도 값 비싼 방법이라고 생각했습니다. 그러나 다시 생각하면 검색을 수행하는 것보다 훨씬 저렴 해 보입니다. –
주기가이 설정에 무엇인지 정의하십시오. – alexraasch
사이클은 셀 배열입니다. 배열의 첫 번째 셀은 시작 셀이 될 것이고 나머지는 언급 된 조건을 준수해야합니다. 세포의 순서는 시작 세포로 끝나야합니다. – Cosmin
"주기의 두 연속 된 셀이 같은 행에 있어야합니다"인 경우 연속되는 세 개의 셀이 같은 행에 있어야하며 "주기의 세 연속 셀이 같은 행에 있지 않아야합니다"라는 조건을 위반해야합니다. A, B 및 C가 세 개의 연속적인 셀이라고 가정합니다. 의미 A와 B는 두 개의 연속 셀이며 B와 C는 두 개의 연속 셀입니다. 첫 번째 조건 A와 B는 같은 행에 있고 B와 C는 같은 행에 있습니다. 이것은 (분명히) A, B 및 C가 모두 같은 행에 있음을 의미합니다. 지금 당장 설치 한 것은 불가능한 것처럼 보입니다. 수정해야합니다. – Spundun