Connect-three puzzle solveability

Question

저는 사각형 그리드를 사용하는 캐주얼 연결형 게임을 작성하고 있습니다. 플레이어는 행이나 열을 슬라이드 (본질적으로 1D에서 회전)하여 동일한 유형의 블록을 3 개 이상 함께 배치하여 일치시킵니다.

게임이 진행됨에 따라 난이도가 높아 지므로 새로운 경기가 될 움직임이 없기 때문에 점수가 올 것입니다.

brute-force 방법 (적어도 O (N^2) 시간)을 사용하는 것 외에도 가능한 이동을 찾는 더 빠른 방법이 있습니까?

Answer 1

당신은 N 보드 및 M에 위치의 수는 O (N 로그 (M))에서 할 수있는 것은 가능한 모양 번호 :

1. O (N 로그 (M)) 각 포인트에 대한 (O (N))의 행과 열 (O (로그 (M))에 사용할 수있는 형태의 맵을 업데이트
   
2. . O (N log (M)) : 각 점 (O (N))에 대해 비슷한 모양이 수직 또는 수평 또는 대각선으로 하나 떨어져 있는지 확인하십시오 (O (1)). 유효한 이동이 가능한지보기 위해 "3 개를 연결하는"행/열 맵 (O (log (M))).

위의 방법으로 불필요하게 검사를 반복하지 않도록 개선 할 수도 있습니다 (두 번째 행의 모양과 아래의 모양은 검사하지 않고 두 번째 열과 오른쪽의 모양은 왼쪽을 검사하지 않음) , 큰 O 비용은 동일합니다.

각 이동 후에 변경된 행/열의 맵을 업데이트하기 만하면 변경된 모양 만 확인하면됩니다. 최악의 경우는 전체 보드가 지워지므로 큰 O이 개선 된 비용은 동일합니다.