t********y
发帖数: 14 | 1 常见的俄罗斯方块，每一个图案都是由4个block组成，现在给定一个N表示N个block，
把所有有效的俄罗斯方块组合都输出出来，（有效的是指block是横着或者竖着连接的
，不是直接斜着连接）。数据结构什么的都自己定义。 |
z*******g
发帖数: 23 | 2 不知道是我没看懂题目还是楼主题目太简单。貌似这个题目是个简单的数学问题啊？ N
/4 =M 可以算出一共有M个方块。每个方块一共有6个变化。所有的方块组合不就是6的M
次方个变化吗。 |
t********y
发帖数: 14 | 3 N=4的俄罗斯方块，一共有7种不同的pieces.任何一种pieces要是能从其他的piece旋转
的来就不能算不同的pieces。 |
r****7
发帖数: 2282 | 4 这不是典型的backtracking么
【在 t********y 的大作中提到】
: N=4的俄罗斯方块，一共有7种不同的pieces.任何一种pieces要是能从其他的piece旋转
: 的来就不能算不同的pieces。
|
w******e
发帖数: 1621 | 5 是你没看懂题目，楼主的题肯定要求正好拼成n*n
N
的M
【在 z*******g 的大作中提到】
: 不知道是我没看懂题目还是楼主题目太简单。貌似这个题目是个简单的数学问题啊？ N
: /4 =M 可以算出一共有M个方块。每个方块一共有6个变化。所有的方块组合不就是6的M
: 次方个变化吗。
|
h**********c
发帖数: 4120 | 6 这个题出的有问题吧
n应该是个square number |
t********y
发帖数: 14 | 7 N没必要是square number， 比方说下面的funtion
vector<俄罗斯方块> findAll(int n).
vector里面的俄罗斯方块不能有重复。 |
M******u
发帖数: 34 | |
h***s
发帖数: 45 | 9 既然不能重复 那n一定是4的倍数而且要小于等于28?
：N没必要是square number， 比方说下面的funtion
：vector<俄罗斯方块> findAll(int n). |
t********y
发帖数: 14 | 10 n = 4 的请看图
我列出了n＝1，2，3，4 的pattern。
n = 1:
1)
*
n=2
2)
**
n = 3
1)
***
2)
*
**
3)
**
*
n=4
1)
****
2)
**
*
*
3)
*
*
**
4)
*
**
*
5)
*
**
*
6)
*
**
*
7)
**
**
【在 h***s 的大作中提到】
: 既然不能重复 那n一定是4的倍数而且要小于等于28?
:
: ：N没必要是square number， 比方说下面的funtion
: ：vector<俄罗斯方块> findAll(int n).
|
|
|
h***s
发帖数: 45 | 11 哦，明白题意了，列出用N个block可以组成的所有unique的形状，block和block只能横
竖连接，传统的俄罗斯方块是N是4的case。 |
t********y
发帖数: 14 | |
w****a
发帖数: 710 | 13 我想问一下如何处理重复。
比如N=2的时候，回溯做有四种情况
第2种
12
第2种
21
第3种
1
2
第4种
2
1
实际上12和21是同一种形状。
请问大牛这题如何干掉重复形状 |
t********y
发帖数: 14 | |
p****a
发帖数: 447 | 15 看不懂
如果
1 2
3 4
和
1 2
3 4
算两种
为什么
1
2 4
3
1
4 2
3
不算？
【在 t********y 的大作中提到】
: n = 4 的请看图
: 我列出了n＝1，2，3，4 的pattern。
: n = 1:
: 1)
: *
: n=2
: 2)
: **
: n = 3
: 1)
|
y*****i
发帖数: 141 | 16 睡前XJB写两句。。
你需要这么几个helper function:
void PushToCornor(Block) //把一个俄罗斯方块推向一个NXN grid的某个角落
void Rotate(Block, direction) //向direction rotate你的方块
attach_another_square_to_this_square() //这个没想清楚signature，意思就是拿到
一个square，给他attach一个legitimate neighboring square
然后递归解：
//以下都是秀逗扣的：
vector generateBlocks(target, current, vector & current_blocks
) {
if (current == target) {
return current_blocks;
}
for(auto block: blocks) {
for(auto square: block) {
square.attach_another_square_to_this_square();
for all 3 rotation directions {
Rotate(block, direction)
PushToCorner(block)
if (find(current_blocks.begin(), cucrent_blocks.end(), block
) == current_blocks.end()) {
current_blocks.push_back(block);
generateBlocks(target, current+1, current_blocks);
current_blocks.pop_back();
}
}
}
}
}
大概就是这么个意思吧。。。直接在这个框里写代码好麻烦。。。 |
