C++实现朋友圈美图：寻找最优轮廓曲线

{"title":"用c++书写这个程序：森森最近想让自己的朋友圈熠熠生辉，所以他决定自己写个美化照片的软件，并起名为森森美图。众所周知，在合照中美化自己的面部而不美化合照者的面部是让自己占据朋友圈高点的绝好方法，因此森森美图里当然得有这个功能。 这个功能的第一步是将自己的面部选中。森森首先计算出了一个图像中所有像素点与周围点的相似程度的分数，分数越低表示某个像素点越“像”一个轮廓边缘上的点。 森森认为，任意连续像素点的得分之和越低，表示它们组成的曲线和轮廓边缘的重合程度越高。为了选择出一个完整的面部，森森决定让用户选择面部上的两个像素点A和B，则连接这两个点的直线就将图像分为两部分，然后在这两部分中分别寻找一条从A到B且与轮廓重合程度最高的曲线，就可以拼出用户的面部了。 然而森森计算出来得分矩阵后，突然发现自己不知道怎么找到这两条曲线了，你能帮森森当上朋友圈的小王子吗？\n\n为了解题方便，我们做出以下补充说明：\n\n图像的左上角是坐标原点(0,0)，我们假设所有像素按矩阵格式排列，其坐标均为非负整数（即横轴向右为正，纵轴向下为正）。\n忽略正好位于连接A和B的直线（注意不是线段）上的像素点，即不认为这部分像素点在任何一个划分部分上，因此曲线也不能经过这部分像素点。\n曲线是八连通的（即任一像素点可与其周围的8个像素连通），但为了计算准确，某像素连接对角相邻的斜向像素时，得分额外增加两个像素分数和的 \n2\n\n 倍减一。例如样例中，经过坐标为(3,1)和(4,2)的两个像素点的曲线，其得分应该是这两个像素点的分数和(2+2)，再加上额外的(2+2)乘以( \n2\n\n -1)，即约为5.66。\n输入格式：\n输入在第一行给出两个正整数N和M（5≤N,M≤100），表示像素得分矩阵的行数和列数。\n\n接下来N行，每行M个不大于1000的非负整数，即为像素点的分值。\n\n最后一行给出用户选择的起始和结束像素点的坐标(X \nstart\n\n ,Y \nstart\n\n )和(X \nend\n\n ,Y \nend\n\n )。4个整数用空格分隔。\n\n输出格式：\n在一行中输出划分图片后找到的轮廓曲线的得分和，保留小数点后两位。注意起点和终点的得分不要重复计算。\n\n输入样例：\n6 6\n9 0 1 9 9 9\n9 9 1 2 2 9\n9 9 2 0 2 9\n9 9 1 1 2 9\n9 9 3 3 1 1\n9 9 9 9 9 9\n2 1 5 4\n输出样例：\n27.04内容：这道题可以使用动态规划来解决。首先，我们可以定义一个二维数组dp，其中dp[i][j]表示从起始点到达坐标(i, j)的最小得分和。然后，我们可以从起始点开始进行动态规划，更新dp数组的值。\n\n具体步骤如下：\n\n1. 初始化dp数组，将所有位置的值都设置为无穷大。\n\n2. 将起始点的值设置为0。\n\n3. 从左上角开始遍历整个图像，更新dp数组的值。遍历顺序可以是任意的，这里我们选择从左上角到右下角的顺序。\n\n4. 对于每个位置(i, j)，我们可以通过以下三种方式更新dp[i][j]的值：\n\n a) 如果(i, j)等于起始点或结束点，则dp[i][j]的值不变。\n\n b) 否则，dp[i][j]的值等于周围8个位置的最小值加上当前位置的得分，并考虑对角位置的额外得分。\n\n5. 最后，我们可以得到dp[endX][endY]的值，即为从起始点到达结束点的最小得分和。\n\n下面是具体的C++代码实现：\n\ncpp\n#include <iostream>\n#include <cmath>\n#include <vector>\nusing namespace std;\n\nint main() {\n int N, M;\n cin >> N >> M;\n \n vector<vector<int>> scores(N, vector<int>(M));\n for (int i = 0; i < N; i++) {\n for (int j = 0; j < M; j++) {\n cin >> scores[i][j];\n }\n }\n \n int startX, startY, endX, endY;\n cin >> startX >> startY >> endX >> endY;\n \n vector<vector<double>> dp(N, vector<double>(M, INFINITY));\n dp[startX][startY] = 0;\n \n for (int i = 1; i < N; i++) {\n for (int j = 1; j < M; j++) {\n if (i == startX && j == startY) {\n continue;\n }\n \n if (i == endX && j == endY) {\n continue;\n }\n \n double minScore = min({dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1], dp[i][j-1], dp[i][j+1], dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]});\n dp[i][j] = minScore + scores[i][j];\n \n if ((i-1 == startX && j-1 == startY) || (i+1 == startX && j+1 == startY)) {\n double extraScore = sqrt(2) * (scores[i-1][j-1] + scores[i+1][j+1]);\n dp[i][j] += extraScore;\n }\n }\n }\n \n double result = dp[endX][endY];\n cout << fixed << setprecision(2) << result << endl;\n \n return 0;\n}\n\n\n希望对你有帮助！