题意:
给一个地图,给定起点和一块连续图形,走一圈围住这个图形求最小步数
本来是要做课件上一道$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=,M=N*N<<;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,g[N][N],sx,sy,a,b;
int dx[]={,-,,,,-,,-},
dy[]={,,,-,,-,-,};
char s[N];
int d[N][N][];
struct Grid{
int x,y,p;
Grid(int a=,int b=,int c=):x(a),y(b),p(c){}
}q[M];
int head,tail,inq[N][N][];
inline void lop(int &x){if(x==M) x=;}
inline bool isInter(int x1,int y1,int x2,int y2){
if(x1<a&&x2==a&&y2>b) return ;
if(x2<a&&x1==a&&y1>b) return ;
return ;
}
void spfa(){
d[sx][sy][]=;
head=tail=;
q[tail++]=Grid(sx,sy,);inq[sx][sy][]=;
while(head!=tail){
Grid u=q[head++];lop(head);
int x=u.x,y=u.y,p=u.p;//printf("\nnow %d %d %d\n",x,y,p);
inq[x][y][p]=;
for(int i=;i<;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<||nx>m||ny<||ny>n||g[nx][ny]) continue;
int np=p^isInter(x,y,nx,ny);//printf("lok %d %d %d\n",nx,ny,np);
if(d[nx][ny][np]>d[x][y][p]+){//printf("new %d %d %d\n",nx,ny,np);
d[nx][ny][np]=d[x][y][p]+;
if(!inq[nx][ny][np])
q[tail++]=Grid(nx,ny,np),lop(tail),inq[nx][ny][np]=;
}
}
}
printf("%d\n",d[sx][sy][]);
}
int main(){
freopen("in","r",stdin);
m=read();n=read();
memset(d,,sizeof(d));
for(int i=;i<=m;i++){
scanf("%s",s+);
for(int j=;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?'\n':' ');
spfa();
}