[线段树] Jzoj P6293 迷宫

痛定思痛。 2021-10-23 10:27 293阅读 0赞

#### Description ####

![Image 1][]

# 题解 #

*  用线段树维护区间\[l,,r\]中，m行格子左边第x行到右边第y行的距离
 *  合并两个的话，枚举中间点k，暴力转移

# 代码 #

1 #pragma GCC optimize(2)
     2 #include <cstdio>
     3 #include <iostream>
     4 #include <cstring>
     5 using namespace std;
     6 const int N=7,M=200001,inf=0x3f3f3f3f;
     7 int n,m,q,a[N][M];
     8 struct tree{ int p[N][N]; }t[M*4];
     9 void pushup(int d)
    10 {
    11     memset(t[d].p,0x3f,sizeof(t[d].p));
    12     for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) t[d].p[i][k]=min(t[d].p[i][k],t[d*2].p[i][j]+t[d*2+1].p[j][k]);
    13 } 
    14 void build(int d,int l,int r) 
    15 {
    16     if (l==r) 
    17     {
    18         for (int i=1;i<=n;i++) t[d].p[i][i]=(a[i][l]==1?1:inf);
    19         for (int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) 
    20         {
    21             int cnt=0;
    22             for (int k=i;k<=j;k++) { if (a[k][l]==0) { cnt=inf; break; } cnt++; }
    23             t[d].p[i][j]=t[d].p[j][i]=cnt;
    24         }
    25         return;
    26     }
    27     int mid=l+r>>1;
    28     build(d*2,l,mid),build(d*2+1,mid+1,r),pushup(d);
    29 }
    30 void modify(int d,int l,int r,int pos)
    31 {
    32     if (l==r) 
    33     {
    34         for (int i=1;i<=n;i++) t[d].p[i][i]=(a[i][l]==1?1:inf);
    35         for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) 
    36         {
    37             int cnt=0;
    38             for (int k=i;k<=j;k++) { if (a[k][l]==0) { cnt=inf;    break; } cnt++;    }
    39             t[d].p[i][j]=t[d].p[j][i]=cnt;
    40         }
    41         return;
    42     }
    43     int mid=(l+r)>>1;
    44     if (pos<=mid) modify(d*2,l,mid,pos);
    45     if (pos>mid) modify(d*2+1,mid+1,r,pos);
    46     pushup(d);
    47 }
    48 tree merge(tree t1,tree t2)
    49 {
    50     tree r;
    51     memset(r.p,0x3f,sizeof r.p);
    52     for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) r.p[i][k]=min(r.p[i][k],t1.p[i][j]+t2.p[j][k]);
    53     return r;
    54 }
    55 tree query(int d,int l,int r,int L,int R)
    56 {
    57     if (L==l&&r==R) return t[d];
    58     int mid=(l+r)>>1;
    59     if (L<=mid&&R>mid) return merge(query(d*2,l,mid,L,mid),query(d*2+1,mid+1,r,mid+1,R));
    60     else if (R<=mid) return query(d*2,l,mid,L,R);
    61     else if (L>mid) return query(d*2+1,mid+1,r,L,R);
    62 }
    63 int main()
    64 {
    65     freopen("maze.in","r",stdin),freopen("maze.out","w",stdout),scanf("%d%d%d",&n,&m,&q);
    66     for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
    67     build(1,1,m);
    68     for (int x,y,X,Y,op;q;q--)
    69     {
    70         scanf("%d%d%d",&op,&x,&y);
    71         if (op==1) a[x][y]^=1,modify(1,1,m,y); else 
    72         {
    73             scanf("%d%d",&X,&Y); tree ans=query(1,1,m,y,Y);
    74             printf("%d\n",ans.p[x][X]==inf?-1:ans.p[x][X]-1);
    75         }
    76     }
    77 }

转载于:https://www.cnblogs.com/Comfortable/p/11342662.html

[Image 1]: