1
모든 Tetrominos의 목록을 생성하려면 어떻게해야합니까? 또는 더 일반적으로, 여러 개의 세포로 제한된 폴리오 노미의 하위 집합을 어떻게 생성 할 수 있습니까?모든 Tetrominos의 목록을 생성하려면 어떻게해야합니까?
A
답변
1
테트 로미노는 모양이다. 컴퓨터는 모양을 직접 표현하지 않으며 숫자를 이진 신호로 표현합니다. 프로그래머는 셰이프를 숫자로 표현하는 방법을 결정합니다. 그들은 비트 맵, 문자열, 열거 형으로 저장할 수 있습니다 ...
특정 도움이 필요하면 훨씬 더 명확한 질문을 작성해야합니다.
나는 왜 당신이 알려진 7 불변의 모양의 목록을 생성하고 싶지 궁금. 테트리스 게임을 쓰고 있다면 변수, 상수 또는 이미지 등의 7 가지 모양을 어딘가에 하드 코딩 할 것입니다.
2
N-omino에 필요한 가장 큰 그리드는 NxN입니다. 그런 다음 모두를 생성하고 회전 및 번역을 제외하십시오.
N-1 단계에서 경로 추적 알고리즘으로 생각할 수 있습니다. 그리드의 왼쪽 위 셀에서 시작하여 거기에서 오른쪽 또는 아래쪽으로 만 이동하면 대부분의 변환과 회전을 피할 수 있습니다. 내가 잘못 본 것이 아니라면 남아있는 유일한 것들은 동형 N- 오노 민입니다. E.G. Right-Down-Left 경로로 만든 tetromino는 Down-Right-Up과 같습니다.
5
이렇게하는 방법에는 여러 가지가 있습니다. 내가 찾은 한 가지 옵션은 재귀 적으로 그리고 더 일반적으로 생각하는 것입니다. 특히 :
- 단일 직사각형은 1-omino입니다.
- n-omino의 경우 블록을 n-omino에 인접하게 두어 (n + 1) -omino를 만들 수 있습니다.
이렇게하면 가능한 모든 n- 오노 아이콘을 재귀 적으로 나열 할 수 있습니다. 그러나 이것은 동일한 n-ominos의 여러 회전과 번역을 생성하므로주의해야합니다. 기준 좌표계를 선택하고 n-omino를 변환하여 시스템의 축과 항상 동일하게 만들 수 있습니다. 일단 그 작업을하면 축을 중심으로 결과 인 n- 오미노를 회전시킨 다음 모든 회전을 생성 할 수 있습니다. 그런 다음이를 정식 위치로 다시 변환합니다.
"Tetrominos"에 대한 스택 오버플로를 검색 한 결과 아무것도 표시되지 않았습니다. 내가 게시 한 후에야 "Polyominoes"를 검색하는 것은 나에게 발생하지 않았다. 그때 나는 보았다 : http://stackoverflow.com/questions/4650762/programming-contest-question-counting-polyominos 나는 그것이 있다고 생각한다. 이 일을 할 수있는 알고리즘을 보니 흥미 롭습니다. 제가 제공 한 링크의 첫 번째 게시물을 조사 할 것입니다. – Mark