我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合特肖 > 访问矩阵 >

给一个矩阵 最多能访问多少个点 c

归档日期:05-09       文本归类:访问矩阵      文章编辑:爱尚语录

  对每个0元素定义其极大扩展矩阵为按以下方法构造的矩阵:先向上扩展,直到遇到1或边界,然后以刚刚得到的边为基准向左右扩展,直到遇到1而不能扩展。比如1000中右下角的0的极大扩展矩阵为最右边的一列,比如0中第二行左数第二列的0的极大扩展矩阵为第一、二行中间的4个0。可以证明最大的全0矩阵必为某个0元素的极大扩展矩阵:最大的全0矩阵(设为A)最上边必定有一些1或边界而导致这个矩阵不能再向上扩展,那么在有1或边界的列上,A中最下面一行的元素的极大扩展矩阵即为A。比如1000中右下角的0的极大扩展矩阵即为一个最大全0矩阵,比如0中第三行中间两个0的极大扩展矩阵均为最大全0矩阵。因此我们可以通过遍历每个0元素的极大扩展矩阵来求得最大全0矩阵。对每个元素保存l,r,h三个值,分别表示从该元素到其极大扩展矩阵最左边一列的的距离、从该元素到其极大扩展矩阵最右边一列的的距离、极大扩展矩阵的高度,可以通过递推求得:如果[i,j](表示从上往下数第i行、从左往右数第j列的元素,下同)=0,那么l[i+1,j]=min{l[i,j],从[i,j]到左边第一个1的距离},r[i+1,j]=min{r[i,j],从[i,j]到右边第一个1的距离},h[i+1,j]=h[i,j]+1,否则l[i+1,j]=从[i,j]到左边第一个1的距离,r[i+1,j]=从[i,j]到右边第一个1的距离,h[i+1,j]=1。最后只需要找出所有元素中(l+r+1)h最大的即可。它的极大扩展矩阵即为最大全0矩阵。

本文链接:http://shawntierney.com/fangwenjuzhen/342.html

上一篇:如何采用访问控制矩阵方法实现rbac

下一篇:没有了