题意：
给一个地图，给定起点和一块连续图形，走一圈围住这个图形求最小步数
本来是要做课件上一道$CF$题，先做一个简化版
只要保证图形有一个点在走出的多边形内就可以了
$hzc:$动态化静态的思想，假设已经有了路线怎么判断合法
点在多边形内是“点变多边形不变”，我们反过来维护多边形变
$f[i][j][0/1]$表示当前走到$(i,j)$，点是否在多边形内
维护一条向右发出的射线，每次走的时候看看有没有穿过射线就行了
因为这是个网格，我们可以规定只有从上面经过才算穿过
然后，这不是$DAG$啊怎么$DP?$
$spfa$大法好
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N=55,M=N*N<<1; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,g[N][N],sx,sy,a,b; int dx[8]={1,-1,0,0,1,-1,1,-1}, dy[8]={0,0,1,-1,1,-1,-1,1}; char s[N]; int d[N][N][2]; struct Grid{ int x,y,p; Grid(int a=0,int b=0,int c=0):x(a),y(b),p(c){} }q[M]; int head,tail,inq[N][N][2]; inline void lop(int &x){if(x==M) x=1;} inline bool isInter(int x1,int y1,int x2,int y2){ if(x1<a&&x2==a&&y2>b) return 1; if(x2<a&&x1==a&&y1>b) return 1; return 0; } void spfa(){ d[sx][sy][0]=0; head=tail=1; q[tail++]=Grid(sx,sy,0);inq[sx][sy][0]=1; while(head!=tail){ Grid u=q[head++];lop(head); int x=u.x,y=u.y,p=u.p;//printf(" now %d %d %d ",x,y,p); inq[x][y][p]=0; for(int i=0;i<8;i++){ int nx=x+dx[i],ny=y+dy[i]; if(nx<1||nx>m||ny<1||ny>n||g[nx][ny]) continue; int np=p^isInter(x,y,nx,ny);//printf("lok %d %d %d ",nx,ny,np); if(d[nx][ny][np]>d[x][y][p]+1){//printf("new %d %d %d ",nx,ny,np); d[nx][ny][np]=d[x][y][p]+1; if(!inq[nx][ny][np]) q[tail++]=Grid(nx,ny,np),lop(tail),inq[nx][ny][np]=1; } } } printf("%d ",d[sx][sy][1]); } int main(){ freopen("in","r",stdin); m=read();n=read(); memset(d,127,sizeof(d)); for(int i=1;i<=m;i++){ scanf("%s",s+1); for(int j=1;j<=n;j++){ g[i][j]=(s[j]=='X'); if(s[j]=='*') sx=i,sy=j; else if(s[j]=='X'&&!a) a=i,b=j; } } //for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) printf("%d%c",g[i][j],j==n?' ':' '); spfa(); }