https://pintia.cn/problem-sets/994805046380707840/problems/994805047395729408
先说一下题意
在一个二维点阵上选两个点s、t，这两个点所在的直线将这个点阵分成两部分
在这两部分里面分别找一条s到t的路径（八连通），这两条路径构成一个闭环，最小化闭环的分数
注意直线所经过的点不属于任何一部分，不能使用
闭环的分数定义为：
每个点都有一个分数，将闭环上的点的分数相加
同时，如果两个点是斜着连通的，那还需要额外加上这两个点分数和的（根号2-1）倍
踩的坑：
1、点的坐标是从0开始计算的
2、向右为x轴，向下为y轴，即给出的点的坐标第一个是列坐标，第二个是行坐标
3、如果路径连续斜着经过的点有3个或更多个，是所有斜着相邻连通的点对都有额外的加分，也就是中间斜着的会计算2次额外加分
这就是在每一个部分做一次spfa
如何判断下一个点v是否在该部分：利用叉积
x到s看作是一个向量，x到t看作是一个向量
两个向量做叉积
所有叉积<0的是一部分，所有叉积>0的是一部分，所有叉积=0的不属于任何一部分
#include<queue> #include<cmath> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define N 101 int n,m; int mp[N][N]; int sx,sy,tx,ty; double pp; struct node { int x,y; }; int dx[8]={-1,1,0,0,-1,-1,1,1}; //上、下、左、右、左上、右上、左下、右下 int dy[8]={0,0,-1,1,-1,1,-1,1}; double d[N][N]; bool vis[N][N]; int tty; double ans; bool judge(int x,int y) //叉积判断是否属于同一部分 { int a1=sx-x,b1=sy-y; int a2=tx-x,b2=ty-y; if(tty==1) return (a1*b2-b1*a2<0); else return (a1*b2-b1*a2>0); } void bfs() { pp=sqrt(2)-1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) d[i][j]=2e9; queue<node>q; node now,nxt; now.x=sx; now.y=sy; d[sx][sy]=mp[sx][sy]; vis[sx][sy]=true; q.push(now); int nx,ny; double nd; while(!q.empty()) { now=q.front(); q.pop(); vis[now.x][now.y]=false; for(int i=0;i<8;++i) { nx=now.x+dx[i]; ny=now.y+dy[i]; if(nx<1 || nx>n || ny<1 || ny>m) continue; if(!judge(nx,ny) && (nx!=tx || ny!=ty)) continue; nd=d[now.x][now.y]+mp[nx][ny]; if(i>=4) nd+=(mp[nx][ny]+mp[now.x][now.y])*pp; //斜着额外的分数 if(nd<d[nx][ny]) { d[nx][ny]=nd; if(nx==tx && ny==ty) continue; if(!vis[nx][ny]) { nxt.x=nx; nxt.y=ny; q.push(nxt); vis[nx][ny]=true; } } } } ans+=d[tx][ty]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&mp[i][j]); scanf("%d%d%d%d",&sy,&sx,&ty,&tx); sy++; sx++; ty++; tx++; tty=1; //标记现在是做哪一部分 bfs(); tty=2;//标记现在是做哪一部分 bfs(); printf("%.2lf",ans-mp[sx][sy]-mp[tx][ty]); //起始位置算了2次 }