블록 퍼즐 해결 C++ 알고리즘

Block Puzzles을 해결하기위한 알고리즘을 만들고 싶지만 최대한 효율적으로 만들고 싶습니다. 나는 이미 쉬운 길을 택했다 (역 추적).블록 퍼즐 해결 C++ 알고리즘

모든 것을 행렬로 나타 냈습니다. 조각이 꼭 들어 맞는 큰 행렬은 처음에는 0이고 조각은 공간이 꽉 찼 으면 1, 그렇지 않으면 공백이면 0입니다. 다음으로 더 효율적인 아이디어는 다음 라인으로 가기 전에 라인이 완료되었는지 항상 확인하는 것입니다. 제가 말하고자하는 것은 조각이
0 1 0 1 1 1 0 1 0 (십자 기호) 일 수 있습니다. 십자가가 구석에 있다면, 프로그램은 쓸모없는 해결책을 위해 전체 역 추적을 할 것이므로, 돌아가서 다른 것을 시도해야합니다.

필자가 말했듯이 필자는 단순한 비효율적 인 역 추적 만 했어도 코드 조각을 제공 할 수 있습니다.
더 좋은 아이디어가 있습니까? 이 경우 동적 프로그래밍을 사용할 수 있습니까?

출처

2013-02-22 Bujanca Mihai

조각을 배치 할 때 배치 된 조각의 0에 연결된 0의 수를 계산하고, 그 수가 가장 작은 배치되지 않은 조각의 1보다 적 으면 배치 된 조각이 잘못된? –

자세한 내용을 알려주십시오. 최대 크기는 얼마입니까? – blackmath

실제 문제는 아니며 단지 시험해보고 싶었습니다. 한계가 [INT_MAX/2] [INT_MAX/2]의 행렬이므로 최대 개수가 INT_MAX라고 가정 해 봅시다. 문제와 관련 없음 :) –

문제를 그래프로 생각하십시오 : 노드는 블록을 배열 할 수있는 다양한 상태이고 가장자리는 한 노드에서 다른 노드로의 가능한 이동입니다. 그러면 솔루션은 현재 위치에서 목표까지의 최단 거리이며 Dijkstra 알고리즘을 사용하여 계산할 수 있습니다.

출처

2013-02-22 21:31:14 user448810

나는 그래프 이론을 배우기 시작했고 현재 Dijkstra의 알고리즘을 읽고있다. 그러나 나는 그것이 무엇을 의미하는지 정확히 이해하기가 약간 어렵다. 나는 그래프가 그들이 읽혀질 때 조각들을 포함 할 것임을 이해한다. 하지만 목표에 도달했을 때 어떻게 알 수 있습니까? 컨테이너에 조각을 넣을 수 있도록 모든 것을 어떻게 표현할 수 있습니까? –

첫 번째 솔루션에서 이미 노드에 대한 표현이 있습니다. 그래프는 인접 목록으로 표시됩니다. 각 노드에서 한 번의 이동으로 도달 할 수있는 모든 노드가 여기에 있습니다. 대상은 원하는 최종 노드입니다. 당신을 포함하여 어떤 경우에는 하나 이상의 가능한 목표가있을 수 있습니다. 따라서 Dijkstra의 알고리즘 대신 단일 소스 최단 경로 알고리즘 (여러 가지가 있습니다)이 필요할 수 있습니다. 너비 우선 검색을 사용하는 알고리즘이 필요할 것이므로 어떤 목표에 도달하자마자 종료 할 수 있습니다. – user448810

블록 퍼즐 해결 C++ 알고리즘

답변

관련 문제