SSLOJ1460最小代价-白红宇

SSLOJ1460最小代价

阅读量：349 次

发布时间：2019-03-04

本文共 2273 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要找到从左上角A到右下角B的路径，使得路径经过的距离和最小。方格中的数字代表距离，0表示移除的点。路径只能向右或向下移动。

方法思路

我们可以使用动态规划来解决这个问题。具体步骤如下：

顺推方法：从起点开始，逐步计算每个点的最小代价。对于每个点(i, j)，我们检查其左边(i-1, j)和上边(i, j-1)的最小代价，选择较小者作为当前点的代价。路径记录从起点到当前点的方向。

逆推方法：从终点开始，反向计算每个点的最小代价。对于每个点(i, j)，我们检查其下边(i+1, j)和右边(i, j+1)的最小代价，选择较小者作为当前点的代价。路径记录从终点到当前点的方向。

路径记录：在顺推或逆推过程中，记录每一步的移动方向，以便最终输出完整的路径。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       #include 
        
         using namespace std;int a[100][100], n, m, b[100][100], c[100][100];int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j]; } } // 初始化边界条件 for (int i = 1; i <= n; ++i) { if (a[i][1] == 0) c[i][1] = 1; else c[i][1] = 2; if (a[i][1] != 0) { b[i][1] = a[i][1]; } else { b[i][1] = 0; } } for (int j = 1; j <= m; ++j) { if (a[1][j] == 0) c[1][j] = 2; else c[1][j] = 1; if (a[1][j] != 0) { b[1][j] = a[1][j]; } else { b[1][j] = 0; } } // 顺推 for (int i = 2; i <= n; ++i) { for (int j = 2; j <= m; ++j) { if (a[i][j] == 0) continue; if (a[i][j-1] == 0 && a[i-1][j] == 0) continue; if (a[i][j-1] == 0) { b[i][j] = b[i-1][j] + a[i][j]; c[i][j] = 1; } else if (a[i-1][j] == 0) { b[i][j] = b[i][j-1] + a[i][j]; c[i][j] = 2; } else { if (b[i-1][j] < b[i][j-1]) { b[i][j] = b[i-1][j] + a[i][j]; c[i][j] = 1; } else { b[i][j] = b[i][j-1] + a[i][j]; c[i][j] = 2; } } } } // 逆推 for (int i = n; i >= 1; --i) { for (int j = m; j >= 1; --j) { if (a[i][j] == 0) continue; if (a[i+1][j] == 0 && a[i][j+1] == 0) continue; if (a[i+1][j] == 0) { b[i][j] = b[i][j+1] + a[i][j]; c[i][j] = 1; } else if (a[i][j+1] == 0) { b[i][j] = b[i+1][j] + a[i][j]; c[i][j] = 2; } else { if (b[i+1][j] < b[i][j+1]) { b[i][j] = b[i+1][j] + a[i][j]; c[i][j] = 1; } else { b[i][j] = b[i][j+1] + a[i][j]; c[i][j] = 2; } } } } // 输出路径 int x = n, y = m; int dx[1001], dy[1001], dxy = 0; while (x > 1 || y > 1) { if (c[x][y] == 1) { dx[dxy] = x; dy[dxy] = y; x--; } else { dx[dxy] = x; dy[dxy] = y; y--; } dxy++; } cout << "(1,1)"; for (int i = dxy - 1; i >= 0; --i) { cout << "->(" << dx[i] << "," << dy[i] << ")"; } cout << endl;}

代码解释

输入处理：读取方格的大小和值。

初始化边界条件：处理起点和终点的特殊情况。

顺推计算：从起点开始，计算每个点的最小代价，并记录路径方向。

逆推计算：从终点开始，反向计算每个点的最小代价，确保结果一致。

路径输出：根据记录的方向，输出完整的路径。

这种方法确保了我们能够找到从A到B的最小代价路径，并且路径被正确记录和输出。

转载地址：http://geue.baihongyu.com/

你可能感兴趣的文章