正題

---

題目大意

一個$n?m$的迷宮，不能往左走，有墻，每次修改一個點或詢問兩個點之間的最短距離。

---

解題思路

考慮到$n$的值很小，所以我們可以用矩陣轉移，然后要求支持修改和查詢所以我們考慮$ddp$。
我們可以用矩陣代替線段樹的權值，然后區間查詢即可。

時間復雜度$O((m+q\log m)n^3)$

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int Size=5,N=201000; struct Matrix{int a[Size][Size]; }c,ans; struct Tree_node{int l,r;Matrix w; }t[N*4]; int n,m,q,v[Size][N],flag; Matrix operator*(const Matrix &a,const Matrix &b) {memset(c.a,0x3f,sizeof(c.a));for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);return c; } struct Seq_Tree{void Build(int x,int l,int r){memset(t[x].w.a,0x3f,sizeof(t[x].w.a));t[x].l=l;t[x].r=r;if(l==r){for(int i=0;i<n;i++){bool up=1,down=1;if(!v[i][l]){continue;}for(int j=0;j<n;j++){if(i+j>=n||!v[i+j][l]) up=0;if(i-j<0||!v[i-j][l]) down=0;if(!up&&!down) break;if(up) t[x].w.a[i+j][i]=j+1;if(down) t[x].w.a[i-j][i]=j+1; }}return;}int mid=(l+r)/2;Build(x*2,l,mid);Build(x*2+1,mid+1,r);t[x].w=t[x*2].w*t[x*2+1].w;}void Ask(int x,int l,int r){if(t[x].l==l&&t[x].r==r){if(!flag) ans=t[x].w,flag=1;else ans=ans*t[x].w;return;}int mid=(t[x].l+t[x].r)/2;if(r<=mid) Ask(x*2,l,r);else if (l>mid) Ask(x*2+1,l,r);else Ask(x*2,l,mid),Ask(x*2+1,mid+1,r);}void Change(int x,int z){if(t[x].l==t[x].r){memset(t[x].w.a,0x3f,sizeof(t[x].w.a));int l=t[x].l;for(int i=0;i<n;i++){bool up=1,down=1;if(!v[i][l]){memset(t[x].w.a[i],0x3f,sizeof(t[x].w.a[i]));continue;}for(int j=0;j<n;j++){if(i+j>=n||!v[i+j][l]) up=0;if(i-j<0||!v[i-j][l]) down=0;if(!up&&!down) break;if(up) t[x].w.a[i+j][i]=j+1;if(down) t[x].w.a[i-j][i]=j+1; }}return;}int mid=(t[x].l+t[x].r)/2;if(z<=mid) Change(x*2,z);else Change(x*2+1,z);t[x].w=t[x*2].w*t[x*2+1].w; } }T; int main() {freopen("maze.in","r",stdin);freopen("maze.out","w",stdout);scanf("%d%d%d",&n,&m,&q);for(int i=0;i<n;i++)for(int j=1;j<=m;j++)scanf("%d",&v[i][j]);T.Build(1,1,m);while(q--){int op,a,b,x,y;scanf("%d%d%d",&op,&a,&b);if(op==1){a--;v[a][b]=!v[a][b];T.Change(1,b);}if(op==2){scanf("%d%d",&x,&y);if(y<b){printf("-1\n");continue;}if(b==y){if(x>a) swap(x,a);x--;a--;flag=0;for(int i=x;i<=a;i++)if(!v[i][b]){flag=1;break;}if(flag) printf("-1\n");else printf("%d\n",a-x);continue;}flag=0;T.Ask(1,b,y-1);x--;a--;bool up=1,down=1;int mins=2147483647;for(int i=0;i<n;i++){if(x+i>=n||!v[x+i][y]) up=0;if(x-i<0||!v[x-i][y]) down=0;if(!up&&!down) break;if(up) mins=min(mins,ans.a[a][x+i]+i);if(down) mins=min(mins,ans.a[a][x-i]+i); } if(mins>n*m){printf("-1\n");continue;}printf("%d\n",mins);}} }

總結

以上是生活随笔為你收集整理的jzoj6293-迷宫【ddp,线段树,矩阵乘法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。