description

analysis

有没有想起【\(NOIP2018\)】保卫王国？
设\(tr[t][x][y]\)表示线段树上的\(t\)节点代表的区间，从最左边列的\(x\)行到最右边列\(y\)行的最小距离
当区间长度为\(1\)时预处理很简单，注意向上走和向下走
合并两个区间\(2t,2t+1\)成\(t\)时，枚举中转点\(z\)，\(tr[t][x][y]=min(tr[2t][x][z]+tr[2t+1][z][y]+1)\)
对其实这个很像弗洛伊德的\(DP\)，就是拿两个区间拼起来
查询就线段树上面合并出一个大区间，然后就可以直接知道答案
修改就修改某个叶子节点代表的区间，重新处理数据，再向上合并

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 200005

#define INF 1000000007

#define ll long long

#define reg register ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll a[6][MAXN];

bool bz[6][MAXN];

ll n,m,q;

struct node

{

	ll f[6][6];

}tr[MAXN<<2],tmp;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

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

	return x*f;

}

inline ll max(ll x,ll y){return x>y?x:y;}

inline ll min(ll x,ll y){return x<y?x:y;}

inline void clear(node &tmp,ll pos)

{

	fo(i,1,n)fo(j,1,n)tmp.f[i][j]=INF;

	fo(i,1,n)

	{

		if (bz[i][pos])tmp.f[i][i]=0;

		fd(j,i-1,1)if (bz[j][pos] && tmp.f[i][j+1]<INF)tmp.f[i][j]=tmp.f[i][j+1]+1;else break;

		fo(j,i+1,n)if (bz[j][pos] && tmp.f[i][j-1]<INF)tmp.f[i][j]=tmp.f[i][j-1]+1;else break;

	}

}

inline node merge(node a,node b)

{

	node c;

	fo(i,1,n)fo(j,1,n)c.f[i][j]=INF;

	fo(k,1,n)fo(i,1,n)fo(j,1,n)

	c.f[i][j]=min(c.f[i][j],a.f[i][k]+b.f[k][j]+1);

	return c;

}

inline void build(ll t,ll l,ll r)

{

	if (l==r)

	{

		clear(tr[t],l);

		return;

	}

	ll mid=(l+r)>>1;

	build(t<<1,l,mid),build((t<<1)+1,mid+1,r);

	tr[t]=merge(tr[t<<1],tr[(t<<1)+1]);

}

inline void modify(ll t,ll l,ll r,ll x,ll y)

{

	if (l==r)

	{

		clear(tr[t],l);

		return;

	}

	ll mid=(l+r)>>1;

	if (x<=mid)modify(t<<1,l,mid,x,y);

	else modify((t<<1)+1,mid+1,r,x,y);

	tr[t]=merge(tr[t<<1],tr[(t<<1)+1]);

}

inline node query(ll t,ll l,ll r,ll x,ll y)

{

	if (l==x && y==r)return tr[t];

	ll mid=(l+r)>>1;

	if (y<=mid)return query(t<<1,l,mid,x,y);

	else if (x>mid)return query((t<<1)+1,mid+1,r,x,y);

	else return merge(query(t<<1,l,mid,x,mid),query((t<<1)+1,mid+1,r,mid+1,y));

}

int main()

{

	//freopen("T1.in","r",stdin);

	freopen("maze.in","r",stdin);

	freopen("maze.out","w",stdout);

	n=read(),m=read(),q=read();

	fo(i,1,n)fo(j,1,m)bz[i][j]=(a[i][j]=read());

	build(1,1,m);

	while (q--)

	{

		ll opt=read(),x=read(),y=read(),xx,yy;

		if (opt==1)bz[x][y]^=1,modify(1,1,m,y,x);

		else

		{

			xx=read(),yy=read();

			if (!bz[x][y] || !bz[xx][yy]){printf("-1\n");continue;}

			tmp=query(1,1,m,y,yy);

			printf("%lld\n",tmp.f[x][xx]<INF?tmp.f[x][xx]:-1ll);

		}

	}

	return 0;

}

巴特西

【JZOJ6293】迷宫

description

analysis

code

最新文章

热门文章