L3-018. 森森美图

本文主要是介绍L3-018. 森森美图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

二、个人理解

Tips：

• 此题第一个难点就是读懂题目，当时费了挺长时间才知道样例是如何算出的。如下图所示，是其面部轮廓，其分数计算过程为
  $score={1+2+2+9+1+（2+2）*（\sqrt{2}-1）+（2+9）*（\sqrt{2}-1）\\+2+1+1+1+（1+1）*（\sqrt{2}-1）}\\=3+17*\sqrt{2}=27.04$
  
• 理解题意后就是基本就会了一半了，接下来主要是在A和B的直线的两边分别用BFS求出其最低分数和的曲线，最后相加便能得出结果（注意A和B只能计算一次，所以最后要减去A和B一次）。
• 除了上述理解外，此题还有几个坑：
  
  1. 补充说明的第一点（即横轴向右为正，纵轴向下为正），要注意这里表示和程序中数组表示可能不同，要记得转化（如在我的程序中，只要将A和B的x、y相反输入即可）；
  2. 因为补充说明的第一点（忽略正好位于连接A和B的直线（注意不是线段）上的像素点）。如何判断三点是否在一个直线上很关键，这里采用三角的行列式公式，即用面积表示，当面积等于0，则其共线；
  3. 还需记住，计算不同部分时，一定要重新初始化。

C++：

#include <iostream>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std;#define inf 0x11111111;struct Point {int x,y;double dis;//重载bool operator !=(const Point &c) const {return x!=c.x||y!=c.y;}
};
queue<Point> q;
int n,m;
double fdis[105][105];//记录从开始点到每个点的最小值
double score[105][105];//接收题目中各点的分数
Point A,B;//起点和终点
int xa,ya,xb,yb;//边界
int dir1[][2]= {{0,1},{1,0},{-1,0},{0,-1}}; //上下左右的方向
int dir2[][2]= {{-1,-1},{1,-1},{-1,1},{1,1}}; //斜的方向
bool tag;//tag=1表示上半部分，tag=0表示下半部分//三角形行列式公式
int cross(Point a,Point b,Point p)
{return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y);
}void inque(Point p)
{//有效值判断if(p.x<1||p.x>n||p.y<1||p.y>m) {return ;}//当有最小值更新，否则returnif(p.dis>=fdis[p.x][p.y]) {return ;}if(tag) {//上半部分，但是包含起点和终点if(p!=A&&p!=B&&cross(A,B,p)<=0) {return ;}} else {//上半部分，但是包含起点和终点if(p!=A&&p!=B&&cross(A,B,p)>=0) {return ;}}fdis[p.x][p.y]=p.dis;//更新//到终点时，就不继续将其入队if(p.x==B.x&&p.y==B.y) {return;}q.push(p);
}void bfs()
{//清空队列while(!q.empty()) {q.pop();}//初始化for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {fdis[i][j]=inf;}}inque(A);while(!q.empty()) {Point now=q.front();q.pop();Point next;//计算上下左右方向for(int i=0; i<4; i++) {next.x=now.x+dir1[i][0];next.y=now.y+dir1[i][1];next.dis=fdis[now.x][now.y]+score[next.x][next.y];inque(next);}//计算斜方向for(int i=0; i<4; i++) {next.x=now.x+dir2[i][0];next.y=now.y+dir2[i][1];next.dis=fdis[now.x][now.y]+score[next.x][next.y]+(score[next.x][next.y]+score[now.x][now.y])*(sqrt(2)-1);inque(next);}}
}
int main()
{cin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>score[i][j];fdis[i][j]=inf;}}cin>>A.y>>A.x>>B.y>>B.x;A.x++;A.y++;B.x++;B.y++;//因为每从0开始，所以都加1，并且对其表示进行了转化A.dis=score[A.x][A.y];double ans=0;tag=false;bfs();ans+=fdis[B.x][B.y];//上半部分tag=true;bfs();ans+=fdis[B.x][B.y];//下半部分printf("%.2f\n",ans-score[A.x][A.y]-score[B.x][B.y]);//最后再减去重复的起点和终点
}

这篇关于L3-018. 森森美图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---