코드 걸림 2009에서이 알고리즘을 설명하십시오.

Question

이것은 round 1B 2009 Problem C "Square Math"의 문제입니다. 컨테스트 분석이 게시되었음을 압니다. 그러나 노드를 두 번 이상 방문 할 수있을 때 BFS를 구현하는 방법을 배우지는 않습니다. DFS 만 사용하여 구현할 수있었습니다. (컨텍스트가 재귀 DFS에 암시 적으로 저장되기 때문에). BFS를 사용하여이를 수행하는 방법?

Answer 1

명시 적으로 컨텍스트를 저장해야합니다.

각 숫자 셀에 대해 해당 셀에서 끝나는 길이 N의 경로에 의해 생성 될 수있는 모든 합계의 테이블을 유지하고 각 합계에 대해 해당 값을 생성하는 최상의 경로를 유지합니다.

N = 1 인 경우이 데이터는 쉽게 생성되고 (각 셀에 대해 하나의 간단한 경로) 주어진 N에 대한 테이블이 주어지면 각 경로를 확장하여 다음 N 개의 테이블을 쉽게 생성 할 수 있습니다.