보드에서 가장 긴 시퀀스 찾기?

Question

다음을 수행하는 함수가 필요합니다.

입력 할 때 각 입력란이 비어 있고 검은 색 돌 또는 흰 돌과 위치가있는 nx 보드가 필요합니다.

출력으로 주어진 위치에서 가장 긴 시퀀스의 길이를 반환합니다. 위치가 비어 있으면 0을 반환합니다.

예를 들어이 보드를 입력 한 경우입니다. (1,0)

BUUUU 
WWWB 
UUUUU 

B 검은 돌은

는, W는 흰색 돌이고 U는 빈 공간이며, 입력 위치이었다 출력하고자

아니면이 판 3. 만약

BUUU 
WUUU 
BUUU 
BUUU 

이고 위치는 0,3 위치는 비어 있기 때문에 출력은 0입니다. 위치가 3,0 인 경우 검정색 열로 인해 출력이 2가됩니다.

시퀀스는 수평, 수직 또는 대각선 일 수 있습니다.

이것은 내가 지금까지 무엇을 가지고 :

나는 위치를 제공하고 있습니다 경우

, I 루프 위, 아래, 양쪽 모두 대각선. 시퀀스가 깨지는 것을 발견 할 때까지 계속 반복합니다. 그런 다음 가장 긴 시퀀스를 반환합니다. 예를 들어, 보드 인 경우 :

WUU 
WWU 
WUU 

이고 위치는 1,0입니다. 나는 옆으로 돌면서 가장 긴 수평 순서가 1이고, 대각선으로 루프를 찾으며, 가장 긴 순서를 찾은 다음 1을 찾은 다음, 가장 긴 순서가 3임을 알기 때문에 3을 반환합니다.

어떻게하면 더 빨리 수행 할 수 있습니까? ? 이 함수는 1 초에 약 1 천만 번 호출해야합니다. 현재 함수는 초당 약 8 백만 번 실행할 수 있습니다.

Answer 1

이것은 O (n^2) 작업입니다. 칠판에 행 우선 순서로 반복합니다. 보드의 각 위치에 대해 각 방향 (수평, 수직 및 대각선)을 사용하여 가장 긴 연속 시퀀스의 3 튜플 카운트를 유지합니다. 점유 된 위치를 만났을 때 연속 시퀀스의 모든 인접 위치를 확인하고 최대 길이를 증가시킵니다 이 위치가 상기 순서에 대한 유효한 추가가되어야한다. 행운을 빌어 요.