按十字题的O(M*N)时间解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

按十字题的O(M*N)时间解

按十字题的O(M*N)时间解# JobHunting - 待字闺中

c*p2012-05-04 07:05

1 楼

题目：
给你一个M*N boolean
矩阵，定义一个操作叫做“在x，y处按键”，这一按将导致x行所有元素和y列所有元素
0变1,1变0，现在给你任意一个矩阵，写个程序打印出任意一系列“按键”操作把它变
成全0矩阵。
几个基本观点：
1.按键顺序不重要
2.一个被按过奇数次的点再被按一次相当于从来没有按过这个点，所以对于给定的图案
，找使之变成全零的解相当于找从全零变成当前图案的按键组合。

M*a2012-05-04 07:05

2 楼

用位操作
boolean row[] , col[]
来记录该行/该列被inverse的次数
所以对于m[x][y]，只要看row[x] + col[y]是偶数还是奇数就行

【在 c****p 的大作中提到】

: 题目：
: 给你一个M*N boolean
: 矩阵，定义一个操作叫做“在x，y处按键”，这一按将导致x行所有元素和y列所有元素
: 0变1,1变0，现在给你任意一个矩阵，写个程序打印出任意一系列“按键”操作把它变
: 成全0矩阵。
: 几个基本观点：
: 1.按键顺序不重要
: 2.一个被按过奇数次的点再被按一次相当于从来没有按过这个点，所以对于给定的图案
: ，找使之变成全零的解相当于找从全零变成当前图案的按键组合。

l*82012-05-04 07:05

3 楼

板凳

c*p2012-05-04 07:05

4 楼

3.简单起见，一个格子被直接按中导致的0-1翻转称为主翻转，和它同行同列的翻转导致
的翻转称为副翻转。那么需要找到一个将主翻转和副翻转区分开来的办法。可以考虑异
或。
4.对于给定图案中的任意一点x,y，可以把它所在的行和列的所有元素相异或。对于M+N
为偶的，若结果为1，则说明该点被按过；对于M+N为奇数的，若结果为0，则说明该点被
按过。
举个例子（我自己写的一个生成图案的函数）
A是图案，D是被按过的键，也即我们要找的解
>> [A,D] = gen_pad(4,4,.2)
A =
1 0 0 1
1 0 0 1
1 1 1 1
0 0 1 0
D =
0 1 0 0
0 1 0 0
0 0 1 0
0 0 0 0
假设解为S矩阵，我们要求出S=D
假设左上角元素为A[1,1]，则
S[1,1]=xor(A[1,1],A[1,2],...A[1,4],A[2,1],A[3,1]...A[4,1])=0；
同理S[1,2]=1
为了降低时间复杂度，我们可以开两个数组xor_row和xor_col，分列记录每行每列的xo
r值，第一遍pass计算每行每列的xor值，第二遍pass算每个点的xor值：
int flag = (M+N) & 1;
int xor_row[M], xor_col[N];
int x,y;
int S[M][N];
set_zeros(xor_row,M);
set_zeros(xor_col,N);
for(x = 0; x{
for(y = 0; y{
xor_row[x] ^= A[x][y];
xor_col[y] ^= A[x][y];
}
}
for(x = 0; x{
for(y = 0; y{
S[x][y] = xor_row[x]^xor_col[y]^A[x][y]^flag;
if(S[x][y])
print_pair(x,y);
}
}
总时间复杂度M*N，空间复杂度M+N

【在 c****p 的大作中提到】

l*82012-05-04 07:05

5 楼

牛！

l*82012-05-04 07:05

6 楼

补充一点：
得到可能的答案之后，需要生成图案并与原图案对比。如果两者不同，说明原图案不
能被翻转为全零矩阵。
比如：
A =
1 0 0
0 0 0
0 0 0
用这个算法得到：
D =
1 0 0
0 0 0
0 0 0
由D生成A'
A' =
1 1 1
1 0 0
1 0 0
A'不等于A
所以输入A无解

导致
+N
点被

【在 c****p 的大作中提到】

: 3.简单起见，一个格子被直接按中导致的0-1翻转称为主翻转，和它同行同列的翻转导致
: 的翻转称为副翻转。那么需要找到一个将主翻转和副翻转区分开来的办法。可以考虑异
: 或。
: 4.对于给定图案中的任意一点x,y，可以把它所在的行和列的所有元素相异或。对于M+N
: 为偶的，若结果为1，则说明该点被按过；对于M+N为奇数的，若结果为0，则说明该点被
: 按过。
: 举个例子（我自己写的一个生成图案的函数）
: A是图案，D是被按过的键，也即我们要找的解
: >> [A,D] = gen_pad(4,4,.2)
: A =

c*p2012-05-04 07:05

7 楼

这个不对。。。。。。。
任何一个图案都是有解的
你给的那个例子，D应该等于：
1 1 1
1 0 0
1 0 0

【在 l*********8 的大作中提到】

: 补充一点：
: 得到可能的答案之后，需要生成图案并与原图案对比。如果两者不同，说明原图案不
: 能被翻转为全零矩阵。
: 比如：
: A =
: 1 0 0
: 0 0 0
: 0 0 0
: 用这个算法得到：
: D =

M*a2012-05-04 07:05

8 楼

看错题了orz

虑异
于M

【在 l*********8 的大作中提到】

l*82012-05-04 07:05

9 楼

我手算了一下：
D =
1 1 1
1 0 0
1 0 0
得到 A
A =
1 1 1
1 0 0
1 0 0

【在 c****p 的大作中提到】

: 这个不对。。。。。。。
: 任何一个图案都是有解的
: 你给的那个例子，D应该等于：
: 1 1 1
: 1 0 0
: 1 0 0

l*82012-05-04 07:05

10 楼

或者说：
由
A1 =
1 1 1
1 0 0
1 0 0
用你的方法算出
D1 =
1 1 1
1 0 0
1 0 0
但如果
A2 =
1 0 0
0 0 0
0 0 0
也得出
D2 =
1 1 1
1 0 0
1 0 0
因为D2 == D1,所以A2也必须等于A1, 矛盾

【在 l*********8 的大作中提到】

: 我手算了一下：
: D =
: 1 1 1
: 1 0 0
: 1 0 0
: 得到 A
: A =
: 1 1 1
: 1 0 0
: 1 0 0

l*82012-05-04 07:05

11 楼

类似的方法构造出两个A矩阵
1 1 1
0 0 0
0 0 0
1 0 0
1 0 0
1 0 0
也得到同样的D

【在 l*********8 的大作中提到】

: 或者说：
: 由
: A1 =
: 1 1 1
: 1 0 0
: 1 0 0
: 用你的方法算出
: D1 =
: 1 1 1
: 1 0 0

l*82012-05-04 07:05

12 楼

上面说的是，不同的A用你的算法可能得到相同的D。
而不同的D也能生成相同的A
比如
D1 =
1 0 0
0 0 0
0 0 0
D2 =
1 1 1
1 0 0
1 0 0
都能生成A
1 1 1
1 0 0
1 0 0
你的算法得到的是一个可行解，不一定是最少按键的解。
不过我觉得你的算法真的很厉害。有解的A应该都能很快找到一个可行解吧。

【在 l*********8 的大作中提到】

: 类似的方法构造出两个A矩阵
: 1 1 1
: 0 0 0
: 0 0 0
: 1 0 0
: 1 0 0
: 1 0 0
: 也得到同样的D

b*v2012-05-04 07:05

13 楼

用解方程的办法可以直接得到解或判断无解，也是O(M*N)时间，O(M+N)空间。我的解法如下：
http://mytechmemo.blogspot.co.uk/2012/05/find-clicks-to-convert
matrix-into.html

c*p2012-05-04 07:05

14 楼

那说明我的算法有问题，我再想想。

【在 l*********8 的大作中提到】

: 我手算了一下：
: D =
: 1 1 1
: 1 0 0
: 1 0 0
: 得到 A
: A =
: 1 1 1
: 1 0 0
: 1 0 0

l*82012-05-04 07:05

15 楼

厉害
我之前也想过用解方程组的方法。不过我想用普通的高斯消去法，时间复杂度 O( (M*N
)^3 ), 空间复杂度 O( (M*N)^2 )

【在 b******v 的大作中提到】

: 用解方程的办法可以直接得到解或判断无解，也是O(M*N)时间，O(M+N)空间。我的解法如下：
: http://mytechmemo.blogspot.co.uk/2012/05/find-clicks-to-convert
: matrix-into.html

r*l2012-05-04 07:05

16 楼

这个题能否用DFS遍历图？每个状态看作一个node，按一次能变到的状态就是它的
neighbor，这样可以构造一个图（一共2^MN个node，每个node有MN个neighbor）。从给
定的那个状态出发，DFS遍历图，直到对应全0的那个状态。
这个图不用事先构造好，从给定的node出发，每走到一个node就构造一个就可以。每个
node可以用一个MN位的二进制数表示，所以很容易可以查到某个node是否已经visited
（已经构造出来了）。
我在G家on site时碰到过这个题（不过当时是说3x3的矩阵），我当时只想出上面的方
法，也不知道好不好。我最后被G拒了，不知道是不是因为这道题没答好，呵呵。

l*82012-05-04 07:05

17 楼

主要时间复杂度太大。m，n稍大的时候，就无法计算了。

visited

【在 r******l 的大作中提到】

: 这个题能否用DFS遍历图？每个状态看作一个node，按一次能变到的状态就是它的
: neighbor，这样可以构造一个图（一共2^MN个node，每个node有MN个neighbor）。从给
: 定的那个状态出发，DFS遍历图，直到对应全0的那个状态。
: 这个图不用事先构造好，从给定的node出发，每走到一个node就构造一个就可以。每个
: node可以用一个MN位的二进制数表示，所以很容易可以查到某个node是否已经visited
: （已经构造出来了）。
: 我在G家on site时碰到过这个题（不过当时是说3x3的矩阵），我当时只想出上面的方
: 法，也不知道好不好。我最后被G拒了，不知道是不是因为这道题没答好，呵呵。

d*u2012-05-04 07:05

18 楼

经典puzzle啊，记得以前acm比赛的时候做过。
http://mathworld.wolfram.com/LightsOutPuzzle.html

l*y2012-05-04 07:05

19 楼

What about
A = [1, 1];
Or
A = [1, 1, 0];

导致
+N
点被

【在 c****p 的大作中提到】

h*g2012-05-04 07:05

20 楼

好象是能在多项式时间内解决，先用线性方程组然后再动态编程，但O(M*N)的时间复杂
度好象很难达到，还没想出更好的办法。

h*g2012-05-04 07:05

21 楼

把思路整理了一下，最终得到：
１当M和N都是偶数时，解总是存在的，列出的线性方程组可以通过MOD ２代数求解，
时间复杂度是O（M＊N）。
２当M和N中有一个是奇数时，问题的结构发生了变化，有的情况下可能不存在解，但
可以通过动态编程来确定是否有解，并找到一个解，动态编程的时间复杂度是O（M＾３
N＾３），空间复杂度是O（M＾３N＾３）。
不知道情形２下面是否有更快的解法。

z*i2012-05-04 07:05

22 楼

以前一个ID给了一个漂亮的解发，怎么不见了？概述如下：
let x_{ij} be the number of pressing/clicking at position (i,j), m_{ij} be
the original input element at (i,j), n_{ij} be the final element after all
pressing/clicking.
1. x_{ij}=R_i+C_j-2x_{ij}+m_{ij}-n{ij}=R_i+C_j+m_{ij}-n{ij} mod 2.
Queistion: how to get R_i(the summation of x_{ij} at row i）and C_j(the
summation of x_{ij} at column j)?
Answer: simply sum x_{ij} for 1<=j2. R_i=nR_i+X+summation of(m_{ij}-n_{ij}) mod 2 at row i.
where X is the summation of x_{ij} for 1<=i<=m, 1<=j<=n.
So we hget
3. (n-1)R_i=X+summation of(m_{ij}-n_{ij}) mod 2 at row i.
Now we need find X to get R_i. Simple sum R_i for all i. We get
4. (n-1)X=mX+summation of (m_{ij}-n_{ij}) mod 2 for all 1<=i<=m,1<=j<=n.
from 4, we have
5. (n-1-m)X=summation of (m_{ij}-n_{ij}) mod 2 for all 1<=i<=m,1<=j<=n.
Note that from 5, X can be computed in time O(mn) since m_{ij} and n_{ij}
are given as inputs.
Then from 3, R_i can be computed in time O(mn) for m R_is, each of which
takes time O(n). Similarily, C_j can be computed in O(mn).
Finally from 1, x_{ij} can be computed in time O(mn).

【在 h********g 的大作中提到】

: 把思路整理了一下，最终得到：
: １当M和N都是偶数时，解总是存在的，列出的线性方程组可以通过MOD ２代数求解，
: 时间复杂度是O（M＊N）。
: ２当M和N中有一个是奇数时，问题的结构发生了变化，有的情况下可能不存在解，但
: 可以通过动态编程来确定是否有解，并找到一个解，动态编程的时间复杂度是O（M＾３
: N＾３），空间复杂度是O（M＾３N＾３）。
: 不知道情形２下面是否有更快的解法。

h*g2012-05-04 07:05

23 楼

您所写的正是我所列的情形１，我写得很清楚，在这种情形下用MOD ２代数可以求解，
不过只有当M，N都是偶数时才能使用，您再仔细推敲一下为什么是这样，另外我提到当
M和N中有一个是奇数时有可能无解，您能否构造一个这种情况出来。

【在 z********i 的大作中提到】

: 以前一个ID给了一个漂亮的解发，怎么不见了？概述如下：
: let x_{ij} be the number of pressing/clicking at position (i,j), m_{ij} be
: the original input element at (i,j), n_{ij} be the final element after all
: pressing/clicking.
: 1. x_{ij}=R_i+C_j-2x_{ij}+m_{ij}-n{ij}=R_i+C_j+m_{ij}-n{ij} mod 2.
: Queistion: how to get R_i(the summation of x_{ij} at row i）and C_j(the
: summation of x_{ij} at column j)?
: Answer: simply sum x_{ij} for 1<=j: 2. R_i=nR_i+X+summation of(m_{ij}-n_{ij}) mod 2 at row i.
: where X is the summation of x_{ij} for 1<=i<=m, 1<=j<=n.

z*i2012-05-04 07:05

24 楼

According to equation 5, (n-1-m)X=summation of (m_{ij}-n_{ij}) mod 2 for all
1<=i<=m,1<=j<=n. 如果这个方程不满足，就无解。比如说，n-m-1是奇数，但
summation of (m_{ij}-n_{ij}) mod 2不为零，为1。
例子：（1）m=1,n=2. [1 0]。（2）m=1,n=4. [1 0 0 0]， or [1 1 1 0], or [1 0 1
1], etc 。(3) m=2,n=3.
1 0 0
0 0 0
所以算法就是先解方程5，如方程无解，原问题无解。然后解方程3，如无解，原问题无
解。最后方程1肯定有解（无系数在x_{ij}前面）。

【在 h********g 的大作中提到】

: 您所写的正是我所列的情形１，我写得很清楚，在这种情形下用MOD ２代数可以求解，
: 不过只有当M，N都是偶数时才能使用，您再仔细推敲一下为什么是这样，另外我提到当
: M和N中有一个是奇数时有可能无解，您能否构造一个这种情况出来。