gmoj 6841. 【2020.11.5提高组模拟】淘淘蓝蓝之树 林

6841. 【2020.11.5提高组模拟】淘淘蓝蓝之树 林

题目大意

有一个n*m的矩阵，里面有一个密封的图形，矩阵中点与点之间八联通，现给定一个起点，求绕该图形一圈后又回到起点的最短路径

Solution

做法通俗易懂

在封闭图形任意一个点处做一个分割线，spfa求出到分割线下方和绕图形一周后到达分割线上方的最短路

最后在分割线上统计答案

要特别考虑分割线刚好穿到起点的情况，此时要换条线

我的方法是原来先往右边拉线，如果拉到起点上了，就把分割线拉到左边（仅供参考）

#include <cstdio>
#include <cstring>
#include <algorithm>
# define N 2001
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int n,m,i,j,x,y,x1,y1,ans,k,l,r,w,fro,to,f[N*N][2],g[N*N],bz[N][N];
char map[N][N];
const int dir[8][2]={{0,1},{1,0},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int main()
{
    open("forest");
    scanf("%d%d
",&n,&m);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            scanf("%c",&map[i][j]);
            if (map[i][j]=='*') x=i,y=j;
            if (map[i][j]=='X') x1=i,y1=j;
        }
        scanf("
");
    }
    if (x1==x && y>y1) fro=0,to=y1;else fro=y1,to=m+1;
    memset(bz,127,sizeof(bz));
    bz[x][y]=0;
    f[1][0]=x;f[1][1]=y; 
    i=0;j=1;
    while (i<j)
    {
        i++;
        x=f[i][0];y=f[i][1];
        if (bz[x][y]<g[i]) continue;
        for (k=0;k<=7;k++)
        {
            if (x+dir[k][0]<=n && x+dir[k][0]>0 && y+dir[k][1]<=m && y+dir[k][1]>0)
            {
                if (g[i]+1>=bz[x+dir[k][0]][y+dir[k][1]] || map[x+dir[k][0]][y+dir[k][1]]=='X') continue;
                if (x+dir[k][0]==x1 && y+dir[k][1]>=fro && y+dir[k][1]<=to) continue; 
                f[++j][0]=x+dir[k][0];
                f[j][1]=y+dir[k][1];
                g[j]=g[i]+1;
                bz[f[j][0]][f[j][1]]=g[j];
            }
        }
    }
    ans=2147483647;
    for (i=fro;i<=to;i++)
    {
        if (!i || i>m) continue;
        for (j=fro;j<=to;j++)
        {
            if (!j || j>m) continue;
        	l=min(i,j);r=max(i,j);
        	w=r-l;
        	if (r-1>=l && r-1>fro) w=r-1-l;
			if (l+1<=r && l+1<to) w=r-l-1; 
			if (l+1<=r-1 && r-1>fro && l+1<to) w=r-l-2;
            ans=min(ans,bz[x1-1][i]+bz[x1+1][j]+w+2);
        }
    }
    printf("%d",ans);
    return 0;
}