249. Matrix
time limit per test: 2
sec.
memory limit per test: 65536
KB
sec.
memory limit per test: 65536
KB
input: standard
output: standard
output: standard
It
is necessary to arrange numbers from 0 to 2^(N+M)-1 in the matrix with
2^N rows and 2^M columns. Moreover, numbers occupying two adjacent
cells must differ only in single bit in binary notation. Cells are
adjacent if they have common side. Matrix is cyclic, i.e. for each row
the leftmost and rightmost matrix cells are considered to be adjacent
(the topmost and the bottommost matrix cells are also adjacent).
is necessary to arrange numbers from 0 to 2^(N+M)-1 in the matrix with
2^N rows and 2^M columns. Moreover, numbers occupying two adjacent
cells must differ only in single bit in binary notation. Cells are
adjacent if they have common side. Matrix is cyclic, i.e. for each row
the leftmost and rightmost matrix cells are considered to be adjacent
(the topmost and the bottommost matrix cells are also adjacent).
Input
The first line of input contains two integers N and M (0<N,M; N+M<=20).
Output
Output file must contain the required matrix in a form of 2^N lines of 2^M integers each.
Sample test(s)
Input
1 1
Output
0 2
1 3
1 3
这道题目要求一个矩阵,使得每个元素和其相邻的元素在二进制表示上相差1位,且每行(每列)开头和每行结尾也二进制表示也相差1位。
考虑二进制的Gary编码，Gary吗为这样一种编码，其元素个数为2的整数幂，且每个相邻的元素在二进制表示上相差1位。
如2个元素的Gary码为：
0
1
2^n个元素的Gary码可以由2^n-1个元素的Gary 码来构成，具体方法如下，将2^n-1个元素的Gary码镜像对称的写在原来的2^n-1个Gary码下面。然后在前2^n-1个Gary 码前面添0， 在后2^n-1个Gary码前面添1
则构成2^n个元素的Gary码，如：
0 0 00
1 1 01
－－－》 1 －－－》 11
0 10
给出一种简单的构造n位Gary码的方法 ，观察可知，第 ith Gary 码可以表示为 i^(i>>1)
则构造n位Gary码的代码为 MaxN=2^n, int data[MaxN]：
那么这道题目可以构造求解，对第一列，构造N位的Gary吗，对第一一行构造M位的Gary码，对第一行的每一个元素，将其左移N位。然后d[i][j]=d[i][0]+d[0][j];(1<=i<2^N,1<=j<2^M)
题目的全部代码如下：