題干：

鏈接：https://ac.nowcoder.com/acm/contest/882/E?&headNav=acm
來源：牛客網
?

Given a maze with N rows and M columns, where bijb_{ij}bij? represents the cell on the i-row, j-th column. If bi,j="1"b_{i, j} = \texttt{"1"}bi,j?="1", it's a wall and can't not be passed. If you are on the cell bi,jb_{i, j}bi,j?, you can go to b(i+1),jb_{(i+1), j}b(i+1),j?, bi,(j?1)b_{i, (j-1)}bi,(j?1)?, or bi,(j+1)b_{i, (j+1)}bi,(j+1)? as long as it's not a wall.

Sometime, a cell may be changed into wall, or vise versa. You need to find out the number of way to pass through the maze starting at some given cell and finishing at some given cell.

?

If the starting cell or finishing cell is a wall, there's clearly no way to pass through the maze.

Note that you can't go back to the cell you just from.

示例1

輸入

復制

2 2 3 00 00 2 1 2 1 1 2 2 1 2

輸出

復制

2 1

題目大意：

有一個 n*m 的 01 矩陣，1 表示不可行，0 代表可行；

每次可以從 (i, j) 走到 (i, j – 1)，(i, j + 1) 和 (i + 1, j)，且不能回到已走過的格子；

有 q 個以下兩種操作：

1、將某個格子的狀態反轉，即1變0，0變1

2、詢問從 (1, x) 走到 (n, y) 的方案數。

1 <= n，q <= 5e4，1 <= m <= 10。

解題報告：

先考慮不帶修改的版本，設矩陣第 i 行第 j 個元素為 A[i][j]；

dp[i][j] 表示從第 i – 1 行經過 (i – 1, j) 走到 (i, j) 的方案數，狀態轉移方程如下：

簡單來說，dp[i][j] 等于 A[i – 1, j] 向左和向右 A[i – 1][k] 都等于 0 的那些 dp[i – 1][k] 的和；

如當 n = 2，m = 6 時：（最上面為第一行）

0	0	0	1	0	0
1	0	1	0	1	0

dp[2][2] = dp[1][1] + dp[1][2] + dp[1][3]；

dp[2][4] = 0

dp[2][6] = dp[1][5] + dp[1][6]。

dp[2]的其余值都是0。

因此第 i 行的 dp 值到第 i + 1 行的 dp 值的轉移可用矩陣 Mi 實現；

如上圖第一行的 dp 值到第二行 dp 值的轉移矩陣 M1：

（注意就算是a[i][j]==1，但是也要更新這一個值，但是其實并沒有什么用，因為后面也會被continue掉）

1	1	1	0	0	0
1	1	1	0	0	0
1	1	1	0	0	0
0	0	0	0	0	0
0	0	0	0	1	1
0	0	0	0	1	1

那么要求從 (1, x) 走到 (n, y) 的方案數，即令 dp[1][x] = 1，求 dp[n + 1][y]；

為什么是 dp[n + 1][y] 而不是 dp[n][y]，因為 dp[n][y] 設定狀態的時候，表示的就是從第 n – 1 行經過 (n – 1, y) 走到 (n, y) 的方案數，故意的漏掉那些從第 n 行走到 (n, y) 的方案數，這樣做的目的也是便于直接統計，而 dp[n + 1][y] 則表示從第 n 行經過 (n, y) 的所有方案數，也就是我們要的答案了。

那么讓矩陣M[i][j]代表的含義是從第i列走到第j列的方案數。

若令矩陣，則就是答案。

再考慮帶修改的版本；

因為每次都會修改一個點，也就是每次只會修改N個矩陣中的一個矩陣，然后再求矩陣的和。

因為矩陣乘法具有可交換性質，所以可以用線段樹維護矩陣乘積：，反轉 (x, y) 的操作即重構 ，為單點修改，時間復雜度為 O(m^3logn)；

根節點維護的就是 ，可 O(1) 回答詢問，總時間復雜度 O(m^3logn)。

注意實現的細節，你如果在結構體中加上l和r節點的話，那矩陣最好重新定義一個結構體，不然的話你pushup就要多寫兩行。如果不多這幾行的話顯然是不對的。（因為你的l和r就被沖掉了）

再貼一個別人的題解：

這樣的話就可以理解為，對于每一個查詢只有dp[1][x]是1，dp[1]的其他值都是0，然后求dp[n+1][y]，

所以就是=(0,0,,,第x位上是1,,0) * 構造的矩陣的第四列，也就是構造的矩陣的M[x][y]項。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 50005 + 5; const ll mod = 1e9 + 7; int n,m,q; struct TREE {int l,r;ll m[12][12]; } tr[MAX<<2]; int a[MAX][13]; TREE mul(TREE a,TREE b) {TREE c;for(int i = 1; i<=m; i++) {for(int j = 1; j<=m; j++) {c.m[i][j] = 0;for(int k = 1; k<=m; k++) {c.m[i][j] = (c.m[i][j] + (a.m[i][k]*b.m[k][j])%mod) % mod;}}}return c; } void modify(int cur,int x) {memset(tr[cur].m,0,sizeof tr[cur].m);for(int i = 1; i<=m; i++) {if(a[x][i] == 1) continue;tr[cur].m[i][i]=1;for(int j = i-1; j>=1&&a[x][j]==0; j--) tr[cur].m[i][j] = 1;for(int j = i+1; j<=m&&a[x][j]==0; j++) tr[cur].m[i][j] = 1;} }void pushup(int cur) {int l = tr[cur].l,r = tr[cur].r;tr[cur] = mul(tr[cur*2],tr[cur*2+1]);tr[cur].l = l,tr[cur].r = r; } void build(int l,int r,int cur) {tr[cur].l = l,tr[cur].r = r;if(l == r) {modify(cur,l);return;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } void update(int tar,int cur) {if(tr[cur].l == tr[cur].r) {modify(cur,tr[cur].l); return;}int mid = (tr[cur].l + tr[cur].r)>>1;if(tar <= mid) update(tar,cur*2);else update(tar,cur*2+1);pushup(cur); } int main() {cin>>n>>m>>q;for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) scanf("%1d",&a[i][j]);}build(1,n,1);while(q--) {int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op == 1) a[x][y] ^= 1,update(x,1);else printf("%lld\n",tr[1].m[x][y]%mod);}return 0 ; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【2019牛客暑期多校训练营（第二场）- E】MAZE（线段树优化dp，dp转矩阵乘法，线段树维护矩阵乘法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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