C++에서 허용되는 왼쪽, 오른쪽, 아래 및 위로 이동이 있는 최소 비용 경로

2D 배열이 있다고 가정합니다. 각 셀이 해당 셀을 방문하는 데 드는 비용을 나타내는 비용으로 구성된 각 셀에서 총 소비 비용이 최소가 되는 왼쪽 상단 셀에서 오른쪽 하단 셀까지의 경로를 찾아야 합니다.

따라서 입력이 다음과 같으면

출력은 (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) =340과 같이 340이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• x, y 좌표 및 거리 매개변수로 셀을 정의합니다.
• 행 x 열 크기의 배열 행렬을 정의합니다.
• 행렬을 inf로 채우기
• 배열 dx 크기 정의:4 :={ - 1, 0, 1, 0}
• 배열 dy 크기 정의:4 :={0, 1, 0, - 1}
• st라는 셀 세트를 정의합니다.
• 셀(0, 0, 0)을 st에 삽입
• 행렬[0, 0] :=그리드[0, 0]
• 동안(st가 비어 있지 않음) −
  • k :=st의 첫 번째 요소
  • st에서 st의 첫 번째 요소 삭제
  • 초기화 i의 경우:=0, i <4일 때 업데이트(i 1만큼 증가), 수행 -
    • x :=k.x + dx[i]
    • y :=k.y + dy[i]
    • isOk(x, y)가 아니면 -
      • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
    • 행렬[x, y]> 행렬[k.x, k.y] + 그리드[x, y]이면 −
      • 행렬[x, y]가 inf와 같지 않으면 -
        • st에서 cell(x, y, matrix[x, y]) 찾기 및 삭제
      • 행렬[x, y] :=행렬[k.x, k.y] + 격자[x, y]
      • 셀(x, y, 행렬[x, y])을 st에 삽입
• 반환 행렬[행 - 1, 열 - 1]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include 네임스페이스 std 사용;#define ROW 5#define COL 5class cell { public:int x, y; 정수 거리; cell(int x, int y, int distance) :x(x), y(y), distance(distance) {}};bool operator<(const cell&a, const cell&b) { if (a.distance ==b.distance) { if (a.x !=b.x) return (a.x =0 &&i =0 &&j  st; st.insert(셀(0, 0, 0)); 행렬[0][0] =그리드[0][0]; 동안 (!st.empty()) { 셀 k =*st.begin(); st.erase(st.begin()); for (int i =0; i <4; i++) { int x =k.x + dx[i]; 정수 y =k.y + dy[i]; (!isOk(x, y)) 계속하면; if (matrix[x][y]> matrix[k.x][k.y] + grid[x][y]){ if (matrix[x][y] !=INT_MAX) st.erase(st.find(cell( x, y, 행렬[x][y])))); 행렬[x][y] =행렬[k.x][k.y] + 그리드[x][y]; st.insert(셀(x, y, 행렬[x][y])); } } } 반환 행렬[행 - 1][열 - 1];}int main() { int grid[ROW][COL] ={ 32, 101, 66, 13, 19, 11, 14, 48, 158, 7, 101, 114, 175, 12, 34, 89, 126, 42, 21, 141, 100, 33, 112, 42, 21}; cout <<해결(그리드, ROW, COL);}

입력

출력:

340