题意:n*m矩阵,n,m<=2e3,矩阵中的1能走到相邻4个1上,0代表障碍,若两个1联通 则只有一条路径
q个询问,q<=2e5,每次询问一个子矩阵中有多少个连通分量?
同一个连通分量中任意两点只有一条路径,于是对相邻的每个1连接一条边,每一个连通分量显然都为一颗树
若子矩形有k个联通分量,因为每个联通分量都为树,则子矩形中点数-边数等于k 利用二维前缀和求出子矩形1的个数(点)和相邻1(边)个数即可 复杂度O(mn+q)
题意:n*m矩阵,n,m<=2e3,矩阵中的1能走到相邻4个1上,0代表障碍,若两个1联通 则只有一条路径
q个询问,q<=2e5,每次询问一个子矩阵中有多少个连通分量?
同一个连通分量中任意两点只有一条路径,于是对相邻的每个1连接一条边,每一个连通分量显然都为一颗树
若子矩形有k个联通分量,因为每个联通分量都为树,则子矩形中点数-边数等于k 利用二维前缀和求出子矩形1的个数(点)和相邻1(边)个数即可 复杂度O(mn+q)