최대 길이가 주어진 최장 경로

Question

도움이 필요합니다.

나는 가능한 한 완벽하게 설명하려고 노력할 것입니다.

제 2 차원 격자가 내 "세계"라고 가정 해 봅시다.

그리드는 다음과 같습니다

회색 사각형 잔디입니다. 녹색 사각형은 도로입니다. 오렌지색 사각형은 사막입니다.

중간에 파란색 사각형이 내 차입니다. 내 차는 5 제곱의 범위 제한이 있습니다. 나는 최대 범위 이하로 도달 할 수있는 모든 사각형을 찾아 강조하고 싶다.

회색 사각형을 가로 질러 운전하는 데 1 개의 비용이 듭니다. 멋진 일은 없어. 그러나 녹색 사각형을 가로 질러 운전하면 +0.5 범위가됩니다. 즉, 처음 두 칸을 주행하면 녹색이되고 최대 거리는 갑자기 6이됩니다. 주황색 사각형을 가로 질러 주행하면 -0.5 범 위가됩니다. 즉, 처음 두 개의 사각형을 주황색으로 주행하면 최대 거리가 4가됩니다.

기본적으로 정사각형으로 운전하면 1 기가 필요하지만 정사각형에 따라 여분의 거리를 줄 수 있습니다 또는 더 작은 범위.

보너스를 고려한 모든 경로 정찰. 내 차의 가장 바깥 쪽을 이처럼 보일 것입니다 :

그래, 나는 검정색 테두리로 표시된 모든 사각형과 그 안에있는 모든 사각형을 찾는 방법을 원합니다. 내 최대 범위 내의 모든 사각형이 강조 표시됩니다.

긴 질문이지만 어떻게해야합니까?

나는 처음부터 "방문한"것으로 표시하고 다시 돌아올 수없는 동일한 광장을 통해 몇 가지 경로를 선택할 수 있기 때문에 폭과 깊이를 처음으로 살펴 보았습니다.

도움말은 크게 도움이 될 것입니다.

여기까지 읽어 주셔서 감사합니다.

/E

Answer 1

당신은 비용이 아니라 보너스의 관점에서 모든 모델은 좀 더 쉽게 나타낼 수 있습니다.

1. 5 일간의 여행 일정이 있습니다.
2. 잔디 한 스퀘어를 통해 주행하는 데는 하루가 걸립니다.
3. 사막 한 광장을 통한 주행은 1.5 일이 걸립니다.
4. 도로 주행 중 각 구간마다 0.5 일이 소요됩니다.

이제 그래프가 단순 해지고 에서 5 일 이상 떨어져 있지 않은 모든 위치를 찾을 수 있습니다.