주어진 제약 조건을 만족하는 주어진 2 차원 배열에서 셀 개수를 찾는 것

Question

(0,0)에서 시작하여 양의 x 및 y 축에서 무한대로 진행하는 2 차원 배열이 주어지면. 주어진 숫자 k> 0, (0,0)에서 도달 할 수있는 셀의 수를 찾으십시오. 매 순간마다 x의 합 + y의 합계 < = k입니다. 이동은 위, 아래, 왼쪽 또는 오른쪽 일 수 있습니다. 주어진 x, y> = 0.
Dfs는 응답을 제공하지만 k의 큰 값에는 충분하지 않습니다. 아무도 나를 위해 더 나은 알고리즘을 도울 수 있습니까?

Answer 1

그들은 k> = x + y로 도달 할 수있는 셀 (x, y)의 수를 계산하도록 요청했다고 생각합니다. 예를 들어, x = 1이면 y는 0과 k-1 사이의 임의의 수를 취할 수 있으며 합계는 < = k가됩니다. 가능한 총 횟수는 다음과 같이 계산할 수 있습니다.

sum(sum(1,y=0..k-x),x=0..k) = 1/2*k²+3/2*k+1 

큰 k의 트릭을 수행 할 수 있어야합니다.

질문에서 "숫자"로 다소 혼란 스럽습니다. 숫자는 9 999를 만드는 3 번처럼 색인을 구성합니다. 셀 (999,888)의 숫자 합은 51입니다. 숫자의 합이 10^9가되게하려면 10^8 자리가 될 수 있습니다. 10^8 (10^8) 개 항목의 결과로 테이블의 정상 크기를 훨씬 능가하는 색인. 그러므로 나는 나의 첫 번째 해석을 추측하고있다. 그게 정확하지 않다면, 조금 더 설명 할 수 있을까요?

편집는 :

좋아, 그래서 내 대답은 그것을 해결하려고하지 않습니다. 나는 좋은 공식이나 대답을 보지 못한다. 나는 색칠/마킹 문제로 접근하고 모든 유효 셀을 표시 한 다음, 다른 모든 기술을 사용하여 모든 부품이 연결되었는지 확인합니다.

나는 뭔가를 생각해 냈지만 너무 지저분하다. 기본적으로 나는 인덱스와 k를 기반으로 한 번에 큰 파트를 표시하려고 시도했습니다. k = 20 인 경우 셀 범위 (0,0.299)를 한 번에 표시 할 수 있습니다 (더 낮은 인덱스는 더 낮은 인덱스 합계를 갖기 때문에) 나머지 범위를 계속 확인합니다. 마지막 숫자 2를 최대 값으로 고정하고 첫 번째 숫자의 최대 값을 찾음으로써 299부터 시작합니다. 그런 다음 나머지 수백 (300-999)에 대한 프로세스를 계속 진행하고 마지막 숫자 만 수정하여 300..389 및 390..398으로 끝냅니다. 그러나, 당신은 이미 그것이 엉망이라고 볼 수 있습니다 ... (그럼에도 불구하고 나는 당신에게 더 좋은 생각을 줄 수 있습니다)

즉시 볼 수있는 또 하나의 문제는 인덱스에서 대칭 적이라는 것입니다. 유효한 셀 (x, y)은 다른 유효한 셀 (y, x)이 있음을 알려줍니다. 마킹 스키마/dfs/bfs에서 이것은 악용 될 수 있습니다.