최적의 4 워드 배치 내부 임의로 크기의 그리드

Question

문제 문 : 네 단어를 감안할 때

, 격자의 영역은 가능한 한 작게되도록 사각형의 M 행 N 그리드 내부에 배치합니다.

단어는 표의 왼쪽에서 오른쪽으로 그리고 위에서 아래로 실행되어야합니다. 글자는 겹칠 수 있지만 추가 단어는 형성 될 수 없습니다. 모든 단어는 하나의 거대한 사슬에서 서로 연결되어야합니다.

"1, 2, 3 및 4"의 4 단어로 구성 할 수있는 예제 그리드. 마지막 그리드가 가장 최적화되어 있습니다.

나는 파이썬을 배우려고 노력하고있어 나는 이것이 내 치아를 절단 할 수있는 좋은 프로그램이 될 것이라고 생각했다.

어떤 아이디어로 이런 문제를 해결하기 위해 내 데이터와 알고리즘을 구조화 할 수 있습니까? 나는 똑바로 대답을 찾고 있지는 않지만 다음과 같은 몇 가지 팁이 있습니다 :

이 라이브러리 또는이 클래스 또는이 데이터 구조를 사용하십시오. 또는 사용 가능한 공간을 통해 이와 같이 반복합니다.

Answer 1

최대 크기 표가 필요한지 생각해보십시오. 단어 one가 two가 three가 four, 그때의 최대 크기 그리드

될 경우

12 X 12이 각 단어에 단부에 배치되는 그리드의 크기 마지막 단어의 마지막 글자를 공유합니다.

이제 공간이 생겼습니다. 우주에서 그 단어들을 어떻게 맞추 었습니까? brute force 방법에 대해 생각해보십시오. 그게 무엇을 수반할까요?

가능한 모든 패턴 조합을 반복 해보십시오. 각 단어를 24 가지 방법으로 배치 할 수 있으며 단어가 4 개이므로 현대 컴퓨터에서 여러 조각으로 나눌 수있는 조합이 약 500,000 개 이상 있습니다. 어떤 패턴이 기준을 실제로 만족하는지 확인하십시오 (문자 일치 등).

일단 무차별 방식을 사용하면 어떻게 수정 할 수 있습니까?

데이터 구조 측면에서 보면 문자를 저장할 수있는 격자 만 있으면됩니다. 중첩 된 목록 구조, 빈약 한 배열, 팬더 또는 다른 많은 것들을 사용할 수 있습니다. 간단히 문제를 해결하고 나중에 수정하십시오.