L3018森森美图（优先队列BFS题解）xiaodangao

题目链接：L3-018 森森美图
题意：这个题的题意很迷，大概意思就是给你一个起点一个终点，然后起点和终点连线的直线将图划分成两部分，然后分别求这两部分的起点到终点的最短路径val相加，需要注意的是，对于边权的计算，这个题边权的计算有点迷，大概就是若a->b->c均不是斜向边，那么总边权为 $a+b+c$ ，如果b+c为斜向边，那么边权为 $a+b+c+(b+c)*(\sqrt 2-1)$
思路：只要理解了题意，思路就很好写了，因为给出了起点和终点，所以用一个向量来表示一条直线，然后就是判断直线将图划分成两部分，设当前点为x，起点为s，终点为t，设向量 $k = x-s$ $m = t-s$ 判断叉积 $k×m$ 的符号，符号相同就是在同一部分。然后就是对于两部分分别利用优先队列bfs求出图最短路径。
$Code:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define inf 1e18
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
using namespace std;

const int N = 1e2+10;
const double eps = 1e-8;

int n,m;
int a[N][N];
struct Point{
    int x,y;
    Point operator-(const Point&a)const{
        return {x-a.x,y-a.y};
    }
    bool operator<(const Point&a)const{
        return a.x>x;
    }
    bool operator==(const Point&a)const{
        return a.x==x and a.y==y;
    }
};
Point s,t;
int cross(Point a,Point b){
    return a.x*b.y-a.y*b.x;
}
Point Vector;
int judge(Point a){
    a = a - t;
    if(cross(a,Vector)>0)return 1;
    else if(cross(a,Vector)==0)return 0;
    return -1;
}
priority_queue<pair<double ,Point> >q;
bool st[N][N];
int l[] = {1,-1,0,0,1,1,-1,-1},r[] = {0,0,-1,1,1,-1,-1,1};
int f;
double  bfs(){
    while(!q.empty())q.pop();
    q.push({-a[s.x][s.y],s});
    st[s.x][s.y] = true;
    while(!q.empty()){
        double  val = q.top().first;
        Point now = q.top().second;
        st[now.x][now.y] = true;
        if(now == t)return -val;
        q.pop();
        rep(i,0,7){
            int idx = l[i] + now.x;
            int idy = r[i] + now.y;
            if(idx >= m||idx < 0||idy >= n||idy < 0)continue;
            if(st[idx][idy])continue;
            Point nows = {idx,idy};
            if(nows == t)goto stk;
            if(judge(nows) != f)continue;
            stk:
            //st[idx][idy] = true;
            double k = a[idx][idy]*1.0;if(i>3)k += (a[idx][idy]+a[now.x][now.y])*(sqrt(2.0)-1);
            //if(nows == t){return -(val-k); }
            q.push({val-k,nows});
        }
    }
    return -1;
}
void solve(){
    read(n);read(m);
    rep(i,0,n-1){
        rep(j,0,m-1)read(a[j][i]);
    }
    read(s.x);read(s.y);read(t.x);read(t.y);
    Vector = {s-t};
//    rep(i,0,n-1){
//        rep(j,0,m-1)printf("%d ",judge({j,i}));pc('\n');
//    }
    f = 1;
    double ans = bfs();
    f = -1;
    //printf("%.3lf\n",ans);
    memset(st,0,sizeof st);
    ans += bfs();
    ans -= 1.0*a[s.x][s.y];ans-=1.0*a[t.x][t.y];
    printf("%.2lf\n",ans);
}
signed main(){solve();return 0;}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。