首页 > 代码库 > POJ 3182 The Grove [DP(spfa) 射线法]
POJ 3182 The Grove [DP(spfa) 射线法]
题意：
给一个地图，给定起点和一块连续图形，走一圈围住这个图形求最小步数
本来是要做课件上一道$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("\nnow %d %d %d\n",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\n",nx,ny,np); if(d[nx][ny][np]>d[x][y][p]+1){//printf("new %d %d %d\n",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\n",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?‘\n‘:‘ ‘); spfa();}
POJ 3182 The Grove [DP(spfa) 射线法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。