e********3 发帖数: 229 | 1 给一个矩阵,每个cell是1或者0. 要求把cell是1的相邻4个cell换成1.
follow up要求要求把cell是1的相邻4个方向,且和这个cell相差曼哈顿距离为K以内的
所有
cell置1. 时间复杂度要求O(MN).
举例:
k = 2,
00000 00100
00000 01110
00100 --> 11111
00000 01110
00000 00100 |
T*****u 发帖数: 7103 | |
e********3 发帖数: 229 | |
I*******g 发帖数: 7600 | 4 先走一遍, 把每个格子的邻居换成:如果原来是0, 换成-1, 如果是1 不变。
在走一遍,把-1 换成1.
O(5MN)
【在 e********3 的大作中提到】 : 给一个矩阵,每个cell是1或者0. 要求把cell是1的相邻4个cell换成1. : follow up要求要求把cell是1的相邻4个方向,且和这个cell相差曼哈顿距离为K以内的 : 所有 : cell置1. 时间复杂度要求O(MN). : 举例: : k = 2, : 00000 00100 : 00000 01110 : 00100 --> 11111 : 00000 01110
|
e********3 发帖数: 229 | 5 怎么得到5MN?K呢?怎么用到K
【在 I*******g 的大作中提到】 : 先走一遍, 把每个格子的邻居换成:如果原来是0, 换成-1, 如果是1 不变。 : 在走一遍,把-1 换成1. : O(5MN)
|
s*******i 发帖数: 698 | 6 你自己题没说清楚 你那个followup也是换4个cell就可以了?我理解也是5MN就可以了
【在 e********3 的大作中提到】 : 怎么得到5MN?K呢?怎么用到K
|
c*******t 发帖数: 123 | 7 你们没有理解楼主。
楼主显然是笔误。
follow up肯定是把四个方向曼哈顿距离内的所有格子设置为1.
brutal force kmn.
但有mn 解法。
了
【在 s*******i 的大作中提到】 : 你自己题没说清楚 你那个followup也是换4个cell就可以了?我理解也是5MN就可以了
|
e********3 发帖数: 229 | 8
了
举例:
k = 2,
00000 00100
00000 01110
00100 --> 11111
00000 01110
00000 00100
【在 s*******i 的大作中提到】 : 你自己题没说清楚 你那个followup也是换4个cell就可以了?我理解也是5MN就可以了
|
h*******e 发帖数: 1377 | 9 如果不要求空间的话 多开个matrix 然后相当于 matrix 0, 1 区间 dfs么。
如果空间严格的话,可以自己在0, 1前面或者后面pigback 1位表示新的matrix的值。
然后dfs, 之后都dfs结束把原先位给抹掉就行了。 |
g*******g 发帖数: 50 | 10 Isn't brute force O(k^2*m*n)?
【在 c*******t 的大作中提到】 : 你们没有理解楼主。 : 楼主显然是笔误。 : follow up肯定是把四个方向曼哈顿距离内的所有格子设置为1. : brutal force kmn. : 但有mn 解法。 : : 了
|
|
|
e********3 发帖数: 229 | 11
大牛是对的...我打漏了2个字:以内,已经补上了...求MN解法
【在 c*******t 的大作中提到】 : 你们没有理解楼主。 : 楼主显然是笔误。 : follow up肯定是把四个方向曼哈顿距离内的所有格子设置为1. : brutal force kmn. : 但有mn 解法。 : : 了
|
c*******t 发帖数: 123 | 12 对,我搞错了。
O(mn)解法我还没想出来。
【在 g*******g 的大作中提到】 : Isn't brute force O(k^2*m*n)?
|
e********3 发帖数: 229 | 13
不是.K=1的时候是MN. 然后把之前得出的结果循环K次就是KMN
【在 g*******g 的大作中提到】 : Isn't brute force O(k^2*m*n)?
|
m*f 发帖数: 3078 | 14 没有看懂楼主的意思,感觉并查集是可能的方案
就像number of islands ii |
e********3 发帖数: 229 | 15
可以具体点么?
应该不是DFS,BFS之类.个人感觉.错了勿喷
【在 m*f 的大作中提到】 : 没有看懂楼主的意思,感觉并查集是可能的方案 : 就像number of islands ii
|
m*f 发帖数: 3078 | 16 我没有看懂你的题意,不过并查集不是dfs/bfs
【在 e********3 的大作中提到】 : : 可以具体点么? : 应该不是DFS,BFS之类.个人感觉.错了勿喷
|
e********3 发帖数: 229 | 17
举了例子还没懂么??? 哪里不懂?
【在 m*f 的大作中提到】 : 我没有看懂你的题意,不过并查集不是dfs/bfs
|
m*f 发帖数: 3078 | 18 我看错了,不过答案给你找来了
http://www.jiuzhang.com/problem/30/
【在 e********3 的大作中提到】 : : 举了例子还没懂么??? 哪里不懂?
|
e********3 发帖数: 229 | 19
不是这题,也不是这答案...这题我知道
【在 m*f 的大作中提到】 : 我看错了,不过答案给你找来了 : http://www.jiuzhang.com/problem/30/
|
h*******e 发帖数: 1377 | 20 hi不知道你看懂我的解法没有我的是o(2mn) 时间复杂度不随着k变化,所以也就是O(
mn)了
【在 e********3 的大作中提到】 : : 不是这题,也不是这答案...这题我知道
|
|
|
e********3 发帖数: 229 | 21
不太明白你的算法.
matrix 0, 1 区间 dfs? 意思就是loop through整个grid然后对没个cell做DFS?
DFS应该不行.因为你对每个cell做DFS的话时间复杂度是k^2. 最后会是MNK^2. 不知道
我有没有理解对你的算法.
【在 h*******e 的大作中提到】 : 如果不要求空间的话 多开个matrix 然后相当于 matrix 0, 1 区间 dfs么。 : 如果空间严格的话,可以自己在0, 1前面或者后面pigback 1位表示新的matrix的值。 : 然后dfs, 之后都dfs结束把原先位给抹掉就行了。
|
c******w 发帖数: 1108 | 22 一个一个cell扫过去,碰到是1的就做k步bfs,bfs的时候遇到零就改成*,遇到*或1就
停止当前branch。
这样每个cell最多被4个bfs扫到。所以复杂度就是mn。
实际上跟区域涂色很相似。
【在 e********3 的大作中提到】 : : 不太明白你的算法. : matrix 0, 1 区间 dfs? 意思就是loop through整个grid然后对没个cell做DFS? : DFS应该不行.因为你对每个cell做DFS的话时间复杂度是k^2. 最后会是MNK^2. 不知道 : 我有没有理解对你的算法.
|
h*******e 发帖数: 1377 | 23 新matrix还有visited数组啊,visited check了就不访问了,每次旧数组遇到新的 1
产生的新曼哈顿区域一定是联通的 如果没有edge的话(matrix 的 edge应该有可能切
断新曼哈顿区域),所以dfs如果碰到有新matrix里面有visited就不必再压入栈了,
做个菱形dfs之后大于edge的不显示就行了。 所以所有点至多只经过一遍。
【在 e********3 的大作中提到】 : : 不太明白你的算法. : matrix 0, 1 区间 dfs? 意思就是loop through整个grid然后对没个cell做DFS? : DFS应该不行.因为你对每个cell做DFS的话时间复杂度是k^2. 最后会是MNK^2. 不知道 : 我有没有理解对你的算法.
|
l*3 发帖数: 2279 | 24 0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
k = 2
是不是有问题?
碰到 (2,2)位置的1以后,做bfs会直接遇到 (2,3)位置的1,然后就停了。这样就会少
涂。
【在 c******w 的大作中提到】 : 一个一个cell扫过去,碰到是1的就做k步bfs,bfs的时候遇到零就改成*,遇到*或1就 : 停止当前branch。 : 这样每个cell最多被4个bfs扫到。所以复杂度就是mn。 : 实际上跟区域涂色很相似。
|
e********3 发帖数: 229 | 25
问题就是停止branch的条件.不能遇到1或者*就停止吧.比如1左边位置是*,这时候不能
停止,因为*的左边和上边可能都需要染色.比如这样:
0000*00
000*1*0
0000*10
对于第三行的1,你bfs时往左走发现有个*,这时候按照染色算法就停止了.但是实际还是
要继续往左染色. 因为这个不是将包围面积染色,而是一定要染k^2个附近的cell.所以
对于每个cell按照这个算法一定要走遍k^2个cell.这样说对不
【在 c******w 的大作中提到】 : 一个一个cell扫过去,碰到是1的就做k步bfs,bfs的时候遇到零就改成*,遇到*或1就 : 停止当前branch。 : 这样每个cell最多被4个bfs扫到。所以复杂度就是mn。 : 实际上跟区域涂色很相似。
|
e********3 发帖数: 229 | 26
看我上面回复.最重要就是停止条件.不能因为visit过就停止,因为我们要的是所有K^2
个cell,而不是某个包围区域.
【在 h*******e 的大作中提到】 : 新matrix还有visited数组啊,visited check了就不访问了,每次旧数组遇到新的 1 : 产生的新曼哈顿区域一定是联通的 如果没有edge的话(matrix 的 edge应该有可能切 : 断新曼哈顿区域),所以dfs如果碰到有新matrix里面有visited就不必再压入栈了, : 做个菱形dfs之后大于edge的不显示就行了。 所以所有点至多只经过一遍。
|
h*******e 发帖数: 1377 | 27 是做 O(M*n) 个 dfs 但正是因为有了 新matrix 的 visited数组的存在总共访问才降
到了 Om*n 新matrix 基本每点都只访问一次。
2
【在 e********3 的大作中提到】 : : 看我上面回复.最重要就是停止条件.不能因为visit过就停止,因为我们要的是所有K^2 : 个cell,而不是某个包围区域.
|
l*3 发帖数: 2279 | 28 我认为应该这么做:
考虑这么一个类似的问题:
m x n 的0 , 1矩阵,要求:
对于每个 "1", 把以这个 “1” 为左上角,以其位置 + (k,k) 为右下角的正方形内所
有点涂色。 要求复杂度 O(m x n)
再说具体一点,我们考虑一个新的问题,这时候对于每个 “1” , 假设位置在 (i,j),
不是要求涂曼哈顿距离了,而是要求 涂 满 (i,j) 为左上角 和 (i+k, j+k) 为右下
角的正方形。
这个问题有什么好处呢?且看如下图形(对应 k = 3 的情形):
3 2 1
2 2 1
1 1 1
如果我们把原先矩阵里面的每个 “1” 都换成 k,然后用 “从左上角开始,以矩形圈
的方式往外扩散(具体参见上图中 "1" 的位置 对应的圈)” 的loop顺序对当前点右
方和下方最
邻近的三个点进行值的update就行了。在当前的 (i,j)位置时,需要update (i+1,j) (
i,j+1) 和 (i+1,j+1) 的值, update方法就是,如果新的点的值小于 "(i,j)位置的值
-1" 时,那么就把他update成 "(i,j)位置的值 - 1"。 这样处理完之后,所有正整数
的地方都是要着色的地方,复杂度是 O(m x n), 不需要额外的空间。
以上算法的关键是,根据涂色要求的本身需要设计一个合理的遍历方式,使得可以不重
复的回头看已经涂过的地方。因为这个类似的变种题更容易观察出这种遍历方式,所以
作为引子先说一下。
这时候考虑原题,就简单了。我们用类似的算法,标记规则是这样的 (假设 k = 3)
0 0 1 0 0
0 1 2 1 0
1 2 3 2 1
0 1 2 1 0
0 0 1 0 0
然后遍历方式是什么呢?是这样的:
从任意一个标记为 k 的点开始 (先预处理矩阵,把所有 “1” 改成 k),以圈状的
方式向矩阵外围遍历(参见上图 “1” 构成的菱形圈),然后每次update 该点周围上
下左右的四个位置。 |
e********3 发帖数: 229 | 29
好吧,看来我误解你的意思了.
你的edge指的是啥?
"碰到有新matrix里面有visited就不必再压入栈". 不明白你这个是怎么保证染遍K^2个
cell的?
【在 h*******e 的大作中提到】 : 新matrix还有visited数组啊,visited check了就不访问了,每次旧数组遇到新的 1 : 产生的新曼哈顿区域一定是联通的 如果没有edge的话(matrix 的 edge应该有可能切 : 断新曼哈顿区域),所以dfs如果碰到有新matrix里面有visited就不必再压入栈了, : 做个菱形dfs之后大于edge的不显示就行了。 所以所有点至多只经过一遍。
|
h*******e 发帖数: 1377 | 30 我又想了一下dfs起始位置应该是菱形的一个尖尖,也就是之前check过的点产生的菱形
touch不到的位置, 因为每次dfs的区域菱形的边 和 正方形的matrix的边 有时候难免
有切割,这个切割先不要管,先做dfs这个新产生的曼哈顿区域一定是联通的。dfs
check一般check两个 一个是 rowI colI 是否越界, 再一个是此点是否访问过, 越
界在现在的情况下暂时不要管,这样能保证dfs出来的区域是联通的, 否则如果被edge
切割无法保证连通性的话,dfs就很难继续了。之后不要显示越界matrix之外的点就好
了。
【在 e********3 的大作中提到】 : : 好吧,看来我误解你的意思了. : 你的edge指的是啥? : "碰到有新matrix里面有visited就不必再压入栈". 不明白你这个是怎么保证染遍K^2个 : cell的?
|
|
|
b***e 发帖数: 1419 | 31 灰常简单:
从所有1所在的位置开始做parallel BFS。具体的讲就是:
// assume input matrix is A
for each (i,j) {
if (A[i,j] == 1) {
M[i,j] = 0;
Q.enque((i, j));
} else {
M[i,j] = null;
}
}
while (Q.notEmpty()) {
(i, j) = Q.deque();
if (M[i+1,j] is null) {
Q.enque(i+1,j);
M[i+1,j] = M[i,j] + 1;
}
if (M[i-1,j] is null) {
Q.enque(i-1,j);
M[i-1,j] = M[i,j] + 1;
}
if (M[i,j+1] is null) {
Q.enque(i,j+1);
M[i,j+1] = M[i,j] + 1;
}
if (M[i,j-1] is null) {
Q.enque(i,j-1);
M[i,j-1] = M[i,j] + 1;
}
}
for each (i, j) {
if (M[i,j] <= k) {
A[i,j] = 1
}
}
【在 e********3 的大作中提到】 : 给一个矩阵,每个cell是1或者0. 要求把cell是1的相邻4个cell换成1. : follow up要求要求把cell是1的相邻4个方向,且和这个cell相差曼哈顿距离为K以内的 : 所有 : cell置1. 时间复杂度要求O(MN). : 举例: : k = 2, : 00000 00100 : 00000 01110 : 00100 --> 11111 : 00000 01110
|
C*7 发帖数: 234 | 32 我觉得他的意思是遇到(2,3)的1就不加入队列了,队列里的其他元素继续bfs。这样
应该没什么问题
【在 l*3 的大作中提到】 : 0 0 0 0 0 0 : 0 0 0 0 0 0 : 0 0 1 1 0 0 : k = 2 : 是不是有问题? : 碰到 (2,2)位置的1以后,做bfs会直接遇到 (2,3)位置的1,然后就停了。这样就会少 : 涂。
|
e********3 发帖数: 229 | 33
不加入的话那那个1怎么办?
【在 C*7 的大作中提到】 : 我觉得他的意思是遇到(2,3)的1就不加入队列了,队列里的其他元素继续bfs。这样 : 应该没什么问题
|
e********3 发帖数: 229 | 34
没明白...假设矩阵就只有1个1,你的算法好像是染遍了整个矩阵?
【在 b***e 的大作中提到】 : 灰常简单: : 从所有1所在的位置开始做parallel BFS。具体的讲就是: : // assume input matrix is A : for each (i,j) { : if (A[i,j] == 1) { : M[i,j] = 0; : Q.enque((i, j)); : } else { : M[i,j] = null; : }
|
e********3 发帖数: 229 | 35
edge
想不通啊...T T略抽象...
【在 h*******e 的大作中提到】 : 我又想了一下dfs起始位置应该是菱形的一个尖尖,也就是之前check过的点产生的菱形 : touch不到的位置, 因为每次dfs的区域菱形的边 和 正方形的matrix的边 有时候难免 : 有切割,这个切割先不要管,先做dfs这个新产生的曼哈顿区域一定是联通的。dfs : check一般check两个 一个是 rowI colI 是否越界, 再一个是此点是否访问过, 越 : 界在现在的情况下暂时不要管,这样能保证dfs出来的区域是联通的, 否则如果被edge : 切割无法保证连通性的话,dfs就很难继续了。之后不要显示越界matrix之外的点就好 : 了。
|
b***e 发帖数: 1419 | 36 打回去再读。M是一个辅助矩阵,A是原始输入。M就是要都染上,里面的数字是到1岛的
最短距离。
【在 e********3 的大作中提到】 : : edge : 想不通啊...T T略抽象...
|
C*7 发帖数: 234 | 37 不是最外层要每个点扫一遍吗,扫到那个1的时候会以它为起点bfs。这个不加入指的是
bfs内循环遇到的时候,不放入队列。大概的样子:
for(i,j){
if(found 1){
bfs
}
}
【在 e********3 的大作中提到】 : : edge : 想不通啊...T T略抽象...
|
e********3 发帖数: 229 | 38
懂了.你的算法应该是对的.
【在 b***e 的大作中提到】 : 打回去再读。M是一个辅助矩阵,A是原始输入。M就是要都染上,里面的数字是到1岛的 : 最短距离。
|
f********y 发帖数: 156 | 39 这个算法强。 M[i,j] 要是初始化为INT_MAX 更清楚些
M[i,j] = null;
【在 b***e 的大作中提到】 : 打回去再读。M是一个辅助矩阵,A是原始输入。M就是要都染上,里面的数字是到1岛的 : 最短距离。
|
e********3 发帖数: 229 | |
|
|
b******b 发帖数: 713 | 41 This solution is great, thanks for provide this!
),
【在 l*3 的大作中提到】 : 我认为应该这么做: : 考虑这么一个类似的问题: : m x n 的0 , 1矩阵,要求: : 对于每个 "1", 把以这个 “1” 为左上角,以其位置 + (k,k) 为右下角的正方形内所 : 有点涂色。 要求复杂度 O(m x n) : 再说具体一点,我们考虑一个新的问题,这时候对于每个 “1” , 假设位置在 (i,j), : 不是要求涂曼哈顿距离了,而是要求 涂 满 (i,j) 为左上角 和 (i+k, j+k) 为右下 : 角的正方形。 : 这个问题有什么好处呢?且看如下图形(对应 k = 3 的情形): : 3 2 1
|
s*********t 发帖数: 36 | 42 觉得这道题就是普通的BFS,只是在加入每个相邻的点时, 加上 distance, 如果
distance+1 = k 就不在继续:
dfs(vector>& mat, int x, int y, int k)
{
queue> que;
que.push({x, y);
queue distance;
distance.push(0);
int dis = 0;
while (!que.empty()) {
int x = que.top().first();
int y = que.top().second();
que.pop();
mat[x][y] = '#';
int dis = distance.top();
distance.pop();
if (dis+1 == k) continue;
vector> adjs = {{1,0}, {-1,0}, {0, 1}, {0, -1}};
for (int i=0; i
int new_x = x + adjs[i].first;
int new_y = y + adsj[i].second;
if (new_x < 0 || new_x > max.size() || new_y <0 || new_y >max[0].
size() || max[x][y] == '#') continue;
que.push({new_x, new_y});
distance.push(dis+1);
}
}
}
不知对不对 |
w****k 发帖数: 755 | 43 曼哈顿半径为k的圆是个固定的模版, 拿它去处理每个点就行了,没必要dfs or bfs. |
l******s 发帖数: 3045 | 44 private static void updateBoard(int[,] board, int k){
int m = board.GetLength(0), n = board.GetLength(1);
Queue queue = new Queue();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(board[i, j] == 1) queue.Enqueue(new int[]{i, j});
while(k-- > 0 && queue.Count != 0){
int count = queue.Count;
while(count-- > 0){
int[] xy = queue.Dequeue();
for(int x = xy[0] - 1; x <= xy[0] + 1; x++)
for(int y = xy[1] - 1; y <= xy[1] + 1; y++){
if(x < 0 || y < 0 || x == m || y == n) continue;
if(Math.Abs(x + y - xy[0] - xy[1]) != 1) continue;
if(board[x, y] == 1) continue;
board[x, y] = 1; queue.Enqueue(new int[]{x, y});
}
}
}
} |
b*****m 发帖数: 77 | 45 这个是不对的, 比如:
* *
*****
*******
***&*&***
*******
*****
* *
&: 原来的1位置, *:新被标记为数字的
当你标记左边那个&的区域后,右边那个&的四面都是not null,因此会漏掉本来右边那
个&的区域。
【在 b***e 的大作中提到】 : 灰常简单: : 从所有1所在的位置开始做parallel BFS。具体的讲就是: : // assume input matrix is A : for each (i,j) { : if (A[i,j] == 1) { : M[i,j] = 0; : Q.enque((i, j)); : } else { : M[i,j] = null; : }
|
a********r 发帖数: 92 | |
m*****k 发帖数: 731 | 47 he used queue, not stack,
what you said won't happen.
use this simple example:
A=[1 0 0 1]
M=[0 null null 0]
then
M=[0 1 null 0]
then
M=[0 1 1 0]
【在 b*****m 的大作中提到】 : 这个是不对的, 比如: : * * : ***** : ******* : ***&*&*** : ******* : ***** : * * : &: 原来的1位置, *:新被标记为数字的 : 当你标记左边那个&的区域后,右边那个&的四面都是not null,因此会漏掉本来右边那
|