http://sokoban.ws/blog Thu, 26 May 2016 05:12:31 +0000 hourly 1 http://wordpress.org/?v=3.1.2 http://sokoban.ws/blog/?p=843#comment-1971 [坑]POI补完计划#1 | qiancl Thu, 26 May 2016 05:12:31 +0000 http://sokoban.ws/blog/?p=843#comment-1971 [...] $《推箱子游戏的一个箱子推动路径搜索算法（二）》$ 2574 #include<cstring> #include<cstdio> #include<vector> #include<algorithm> using namespace std; #define N 110 const int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; char mp[N][N];int i,j,l,r,top,ans,Po[N][N],Now,stx,ex,now,ey,bx,by,sty,k,m,n,x,y,po[N][N],bcc,clock,pre[N][N]; bool cut[N][N],mk[N][N][4];vector<int>bl[N][N]; inline void add(int x,int y,int bcc){ for(int i=0;i<bl[x][y].size();++i)if(bl[x][y][i]==bcc)return; bl[x][y].push_back(bcc); } struct edge{int x1,y1,x2,y2;}S[N*N]; struct node{int x,y,d;}q[N*N*4]; int dfs(int x,int y,int fx,int fy){ int lw=pre[x][y]=++clock,cld=0;Po[x][y]=Now; for(int i=0;i<4;++i){ int xx=x+dx[i],yy=y+dy[i]; if(mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||(xx==fx&&yy==fy))continue; edge e=(edge){x,y,xx,yy}; if(!pre[xx][yy]){ S[++top]=e,++cld;int lv=dfs(xx,yy,x,y); lw=min(lw,lv); if(lv>=pre[x][y]){ cut[x][y]=1,++bcc; for(;;){ edge o=S[top--]; add(o.x1,o.y1,bcc),add(o.x2,o.y2,bcc); if(o.x1==x&&o.y1==y&&o.x2==xx&&o.y2==yy)break; } } }else if(pre[xx][yy]<pre[x][y])S[++top]=e,lw=min(lw,pre[xx][yy]); } if(fx<0&&fy<0&&cld==1)cut[x][y]=0; return lw; } void dfs1(int x,int y){ po[x][y]=now;for(int i=0;i<4;++i){ int xx=x+dx[i],yy=y+dy[i]; if(po[xx][yy]||mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='P')continue; dfs1(xx,yy); } } int main(){ for(scanf("%d%d",&n,&m),i=1;i<=n;++i)scanf("%s",mp[i]+1); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!pre[i][j]&&mp[i][j]!='S')++Now,dfs(i,j,-1,-1); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!po[i][j]&&mp[i][j]!='S'&&mp[i][j]!='P')++now,dfs1(i,j); for(i=1;i<=n;++i)for(j=1;j<=m;++j) if(mp[i][j]=='M')stx=i,sty=j; else if(mp[i][j]=='P')bx=i,by=j; else if(mp[i][j]=='K')ex=i,ey=j; for(l=1,i=0;i<4;++i)if(po[stx][sty]==po[bx+dx[i]][by+dy[i]])q[++r]=((node){bx,by,i}),mk[bx][by][i]=1; for(;l<=r;++ans){ int k=r-l+1; for(j=1;j<=k;++j){ int x=q[l].x,y=q[l].y,d=q[l++].d,xx,yy; if(x==ex&&y==ey)return printf("%d",ans),0; for(i=0;i<4;++i){ if(cut[x][y]){ bool flag=0; for(int p=0;p<bl[x+dx[i]][y+dy[i]].size()&&flag==0;++p) for(int q=0;q<bl[x+dx[d]][y+dy[d]].size()&&flag==0;++q)if(bl[x+dx[i]][y+dy[i]][p]==bl[x+dx[d]][y+dy[d]][q])flag=1; if(flag&&mp[xx=x-dx[i]][yy=y-dy[i]]!='S'&&xx>=1&&xx<=n&&yy>=1&&yy<=m) if(!mk[xx][yy][i])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1; }else if((!mk[xx=x-dx[i]][yy=y-dy[i]][i])&&(mp[xx][yy]!='S')&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&Po[x+dx[i]][y+dy[i]]==Po[x+dx[d]][y+dy[d]])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1; } } } puts("NO"); } [...] [...] $《推箱子游戏的一个箱子推动路径搜索算法（二）》$ 2574 #include<cstring> #include<cstdio> #include<vector> #include<algorithm> using namespace std; #define N 110 const int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; char mp[N][N];int i,j,l,r,top,ans,Po[N][N],Now,stx,ex,now,ey,bx,by,sty,k,m,n,x,y,po[N][N],bcc,clock,pre[N][N]; bool cut[N][N],mk[N][N][4];vector<int>bl[N][N]; inline void add(int x,int y,int bcc){ for(int i=0;i<bl[x][y].size();++i)if(bl[x][y][i]==bcc)return; bl[x][y].push_back(bcc); } struct edge{int x1,y1,x2,y2;}S[N*N]; struct node{int x,y,d;}q[N*N*4]; int dfs(int x,int y,int fx,int fy){ int lw=pre[x][y]=++clock,cld=0;Po[x][y]=Now; for(int i=0;i<4;++i){ int xx=x+dx[i],yy=y+dy[i]; if(mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||(xx==fx&&yy==fy))continue; edge e=(edge){x,y,xx,yy}; if(!pre[xx][yy]){ S[++top]=e,++cld;int lv=dfs(xx,yy,x,y); lw=min(lw,lv); if(lv>=pre[x][y]){ cut[x][y]=1,++bcc; for(;;){ edge o=S[top--]; add(o.x1,o.y1,bcc),add(o.x2,o.y2,bcc); if(o.x1==x&&o.y1==y&&o.x2==xx&&o.y2==yy)break; } } }else if(pre[xx][yy]<pre[x][y])S[++top]=e,lw=min(lw,pre[xx][yy]); } if(fx<0&&fy<0&&cld==1)cut[x][y]=0; return lw; } void dfs1(int x,int y){ po[x][y]=now;for(int i=0;i<4;++i){ int xx=x+dx[i],yy=y+dy[i]; if(po[xx][yy]||mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='P')continue; dfs1(xx,yy); } } int main(){ for(scanf("%d%d",&n,&m),i=1;i<=n;++i)scanf("%s",mp[i]+1); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!pre[i][j]&&mp[i][j]!='S')++Now,dfs(i,j,-1,-1); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!po[i][j]&&mp[i][j]!='S'&&mp[i][j]!='P')++now,dfs1(i,j); for(i=1;i<=n;++i)for(j=1;j<=m;++j) if(mp[i][j]=='M')stx=i,sty=j; else if(mp[i][j]=='P')bx=i,by=j; else if(mp[i][j]=='K')ex=i,ey=j; for(l=1,i=0;i<4;++i)if(po[stx][sty]==po[bx+dx[i]][by+dy[i]])q[++r]=((node){bx,by,i}),mk[bx][by][i]=1; for(;l<=r;++ans){ int k=r-l+1; for(j=1;j<=k;++j){ int x=q[l].x,y=q[l].y,d=q[l++].d,xx,yy; if(x==ex&&y==ey)return printf("%d",ans),0; for(i=0;i<4;++i){ if(cut[x][y]){ bool flag=0; for(int p=0;p<bl[x+dx[i]][y+dy[i]].size()&&flag==0;++p) for(int q=0;q<bl[x+dx[d]][y+dy[d]].size()&&flag==0;++q)if(bl[x+dx[i]][y+dy[i]][p]==bl[x+dx[d]][y+dy[d]][q])flag=1; if(flag&&mp[xx=x-dx[i]][yy=y-dy[i]]!='S'&&xx>=1&&xx<=n&&yy>=1&&yy<=m) if(!mk[xx][yy][i])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1; }else if((!mk[xx=x-dx[i]][yy=y-dy[i]][i])&&(mp[xx][yy]!='S')&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&Po[x+dx[i]][y+dy[i]]==Po[x+dx[d]][y+dy[d]])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1; } } } puts("NO"); } [...]

]]> http://sokoban.ws/blog/?p=298#comment-1970 [坑]POI补完计划#1 – qiancl Thu, 26 May 2016 04:48:21 +0000 http://sokoban.ws/blog/?p=298#comment-1970 [...] $《推箱子游戏的一个箱子推动路径搜索算法》$ [...] [...] $《推箱子游戏的一个箱子推动路径搜索算法》$ [...]

]]> http://sokoban.ws/blog/?p=2254#comment-1969 HZF Sat, 20 Feb 2016 00:39:00 +0000 http://sokoban.ws/blog/?p=2254#comment-1969 感谢杨兄的分享和精彩的分析。 感谢杨兄的分享和精彩的分析。

]]>