bzoj 2574 [Poi1999]Store-Keeper

bzoj 2574 [Poi1999]Store-Keeper

​​ Description 有一个仓库被分成n*m 个矩形区域，如果两个区域有一条公共边，则被认为这两个区域相邻。包裹都放在一个区域中，剩余的区域或者空闲或者被集装箱占有，这是因为集装箱太重，仓库管理员不能将集装箱搬走。仓库管理员目是是要将包裹从开始的P区域移动到最后的K区域。他可以从空区域走到与之相邻的一个空区域。当仓库管理员走到与包裹相邻的区域时，它可以推动包裹，具体的推动方法如下所示：

读入一个储藏表，开始位置为仓库管理员，最后位置为包裹移动的位置

Input S – 集装箱,

M –仓库管理员的位置,

P –包裹开始的位置,

K –包裹最后的位置,

w –空区域.

S, M, P 和 K 在文件中只出现一次.

第一行有两个用单个空格分隔的正整数n,m<=100. 接下来是货物存放二维表.共N行，每行为M 个字母组成的单词，字母分别是S, M, P, K, w. 第i单词的第j个位置表示第i行第j列区域的信息，可能是如下内容:

Output 如果包裹不能移动到目的位置，则写入NO。

如果包裹能移动到目的位置，则写入最小的移动次数。

Sample Input 10 12

SSSSSSSSSSSS

SOutput 7

HINT Source

​​javascript:void(0)​​

同上面一篇 只不过这里u求最少步数于是我将visit变成最少需要几步到达那个状态 因为是bfs 保证了最短路到达 为了区分状态 我最后a需要-1

#include#include#include#include#include#define fi first#define se second#define pa pair#define mp(x,y) make_pair(x,y)using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}const int N=110;int dx[]={1,-1,0,0},dy[]={0,0,1,-1};bool vis[N][N];char s[N][N];int n,m,tot,dfn[N][N],low[N][N],fa[N*N<<1],visit[N][N][4],cnt,id[N][N];int stx,sty,edx,edy,px,py,top,num;pa q[N*N];inline void dfs(int x,int y,int frx,int fry){ dfn[x][y]=low[x][y]=++num;q[++top]=mp(x,y); for (int i=0;i<=3;++i){ int x1=x+dx[i],y1=y+dy[i]; if (x1<1||x1>n||y1<1||y1>m) continue; if (s[x1][y1]!='w') continue; if (x1==frx&&y1==fry) continue; if (!dfn[x1][y1]){ dfs(x1,y1,x,y);low[x][y]=min(low[x][y],low[x1][y1]); if (low[x1][y1]>=dfn[x][y]){ ++tot;fa[tot]=id[x][y];static pa v; do{ v=q[top--];fa[id[v.fi][v.se]]=tot; }while(id[v.fi][v.se]!=id[x1][y1]); } }else low[x][y]=min(low[x][y],dfn[x1][y1]); }}inline bool check(int x,int y){ return fa[x]==fa[y]||fa[fa[x]]==y||fa[fa[y]]==x;}inline void init(){ static queue q;q.push(mp(px,py));vis[px][py]=1;vis[stx][sty]=1; while(!q.empty()){ int x=q.front().fi,y=q.front().se;q.pop(); for (int i=0;i<=3;++i){ int x1=x+dx[i],y1=y+dy[i];if (s[x1][y1]!='w') continue; if (x1<1||x1>n||y1<1||y1>m) continue; if (vis[x1][y1]) continue;vis[x1][y1]=1;q.push(mp(x1,y1)); } }}struct node{int x,y,s;};inline void gao(){ static queueq; for (int i=0;i<=3;++i){ int x=stx+dx[i],y=sty+dy[i]; if (x<1||x>n||y<1||y>m) continue; if (s[x][y]!='w') continue;if (!vis[x][y]) continue; q.push((node){stx,sty,i});visit[stx][sty][i]=1; } while(!q.empty()){ static node v;v=q.front();q.pop(); int x=v.x,y=v.y,S=v.s; int x1=x+dx[S^1],y1=y+dy[S^1]; if (s[x1][y1]=='w'&&!(x1<1||x1>n||y1<1||y1>m)&&!visit[x1][y1][S]){ visit[x1][y1][S]=visit[x][y][S]+1;q.push((node){x1,y1,S}); }int nowx=x+dx[S],nowy=y+dy[S]; for (int i=0;i<=3;++i){ int x1=x+dx[i],y1=y+dy[i]; if (x1<1||y1<1||x1>n||y1>m) continue; if (s[x1][y1]!='w') continue; if (!check(id[x1][y1],id[nowx][nowy])) continue; if (visit[x][y][i]) continue; visit[x][y][i]=visit[x][y][S]; q.push((node){x,y,i}); } }}int main(){ freopen("bzoj2574.in","r",stdin); n=read();m=read();tot=n*m; for (int i=1;i<=n;++i) scanf("%s",s[i]+1); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) {id[i][j]=++cnt; if (s[i][j]=='M') px=i,py=j,s[i][j]='w'; if (s[i][j]=='P') stx=i,sty=j,s[i][j]='w'; if (s[i][j]=='K') edx=i,edy=j,s[i][j]='w'; } if (stx==edx&&sty==edy) {puts("0");return 0;} dfs(px,py,0,0); init(); gao();int ans=0x3f3f3f3f; for (int i=0;i<=3;++i){ if (visit[edx][edy][i]) ans=min(ans,visit[edx][edy][i]); } if(ans==0x3f3f3f3f) puts("NO");else printf("%d\n",ans-1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。