[USACO17DEC]Push a Box

https://www.zybuluo.com/ysner/note/1293166

题面

解析

挺不错的一道图论码量题。

可以借此回顾一下\(noip2013\)华容道。

思路和华容道差不多。

照洛谷数据规模看，暴搜可能有\(\frac{1}{3}\)的分数。。。

设\(f[w][i][j]\)表示箱子在点\((i,j)\)时，人能否到达\(w\)方向（即\(0/1/2/3\)，表示上下左右）。

那么我们可以先从人出发\(BFS\)一遍，预处理出未推箱子时的\(f[w][i][j]\)。

注意箱子所在点是可以多次更新的。

然后开始推箱子，每次有两种决策：

换个方向
照原方向推一格

决策可不可行肯定要预处理出来，毕竟\(n\)是\(10^6\)级别的。

显然如果能换方向，就说明换方向的前后两点在同一点双联通分量中。

这玩意儿从人的出发点跑一遍\(Tarjan\)就能预处理出来。

推一格这个操作可以直接转移。

注意边界都要赋为\(\#\)。（尤其是每行末尾）

细节挺多，蒟蒻调了两个多小时。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#include<vector>

#define ll long long

#define re register

#define il inline

#define pb(a) push_back(a)

#define gc() getchar()

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=1644;

int n,m,q,sx,sy,rx,ry,dfn[N*N],low[N*N],top,sta[N*N],tot,Id[N][N];

int mx[4]={1,-1,0,0},my[4]={0,0,1,-1};

bool f[4][N][N],vis[N][N];

char mp[N][N];

struct dat{int x,y,w;};

queue<dat>Q;

vector<int>c[N*N];

il int id(re int x,re int y){return Id[x][y];}

il int gi()

{

  re int x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=gc();

  if(ch=='-') t=-1,ch=gc();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=gc();

  return x*t;

}

il void Tarjan(re int x,re int y,re int fx,re int fy)

{

  re int u=id(x,y);

  sta[++top]=u,dfn[u]=low[u]=++tot;

  fp(i,0,3)

    {

      re int xx=x+mx[i],yy=y+my[i],v=id(xx,yy);

      if(mp[xx][yy]=='#') continue;

      if(xx==fx&&yy==fy) continue;

      if(!dfn[v])

    {

      Tarjan(xx,yy,x,y);

      low[u]=min(low[u],low[v]);

          if(low[v]>=dfn[u])

        {

          ++tot;re int g;

          do{g=sta[top--];c[g].pb(tot);}while(g^v);

          c[u].pb(tot);

        }

    }

      else low[u]=min(low[u],dfn[v]);

    }

}

il void BFS1()

{

  Q.push((dat){rx,ry,0});vis[rx][ry]=1;

  while(!Q.empty())

    {

      re int x=Q.front().x,y=Q.front().y,u=id(x,y);Q.pop();

      fp(i,0,3)

    {

      re int xx=x+mx[i],yy=y+my[i],v=id(xx,yy);

      if(mp[xx][yy]=='#'||vis[xx][yy]) continue;

      if(xx==sx&&yy==sy) {f[i^1][xx][yy]=1;continue;}

      vis[xx][yy]=1;Q.push((dat){xx,yy,0});

    }

    }

}

il int check(re int x,re int y,re int xx,re int yy)

{

  re int u=id(x,y),v=id(xx,yy);

  for(re int i=0;i<c[u].size();++i)

    for(re int j=0;j<c[v].size();++j)

      if(c[u][i]==c[v][j]) return 1;

  return 0;

}

il void BFS2()

{

  fp(i,0,3) if(f[i][sx][sy]) Q.push((dat){sx,sy,i});

  while(!Q.empty())

    {

      re int x=Q.front().x,y=Q.front().y,w=Q.front().w,u=id(x,y);Q.pop();

      fp(i,0,3)

    {

          if(f[i][x][y]) continue;

      re int xx=x+mx[i],yy=y+my[i];

      if(mp[xx][yy]=='#') continue;

      if(check(x+mx[w],y+my[w],xx,yy)) f[i][x][y]=1,Q.push((dat){x,y,i});

    }

    {

      re int xx=x+mx[w^1],yy=y+my[w^1];///yy=y+mx???????

      if(mp[xx][yy]=='#') continue;

      if(!f[w][xx][yy]) f[w][xx][yy]=1,Q.push((dat){xx,yy,w});

    }

    }

}

int main()

{

  n=gi();m=gi();q=gi();

    memset(mp,'#',sizeof(mp));

    fp(i,1,n) scanf("%s",mp[i]+1),mp[i][m+1]='#';

  fp(i,1,n)

    fp(j,1,m)

    {

    if(mp[i][j]=='A') rx=i,ry=j,mp[i][j]='.';

    else if(mp[i][j]=='B') sx=i,sy=j,mp[i][j]='.';

    Id[i][j]=(i-1)*m+j;

    }

  Tarjan(rx,ry,0,0);

  BFS1();

  BFS2();

  while(q--)

    {

      re int x=gi(),y=gi(),tag=(sx==x&&sy==y);

      fp(i,0,3) tag|=f[i][x][y];

      puts(tag?"YES":"NO");

    }

  return 0;

}

巴特西

[USACO17DEC]Push a Box

https://www.zybuluo.com/ysner/note/1293166

题面

解析

最新文章

热门文章