可用分押宝游戏火热进行中...	专题改版：Java Web 专题

关于俄罗斯方块&回溯法

楼主mmmcd（超超）2003-02-04 12:51:20 在专题开发/技术/项目 / 数据结构与算法提问

有如下类型俄罗斯方块:
**** * * ** ** **
*** *** ** ** **
方块可任意旋转
用回溯法寻找铺满某个矩形的方案数,矩形长宽不大于6
程序如何编才较简便? 问题点数：100、回复次数：34Top

1 楼finalvictory（打倒小日本！）回复于 2003-02-04 15:16:56 得分 5

哦？这个问题比较有意思，但是没有想过。

要是我就倒过来找：把矩形拆成方块，而不是用方块组成矩形，这样可能会比较方便吧，如果不要求全部解的话。Top

2 楼nhzp（怒火之袍）回复于 2003-02-04 18:50:14 得分 5

我的初步想法就是按行（或列）扫描未被占的格子，然后用可能的方块种类回溯就行了Top

3 楼sgoat（一天到晚游泳的鱼）回复于 2003-02-04 21:29:29 得分 5

最好不要用回朔,这样很慢.如果只是要找一个可能的话,可以用贪心法试下,
Top

4 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-02-05 00:03:48 得分 5

如果填充超出矩形边界没关系吧？
如果长宽没有限制很小，最好别用回溯，是NP规模的。判断“下左右”相邻的空格是否被封闭来回溯，除此我也没想什么好的方法。:)
UP，UP！Top

5 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-02-05 00:09:53 得分 0

强调：判断时只需判断"下左右"相邻的空格组成的区域即可，你考虑下。Top

6 楼xdspower（杂食菜熊）回复于 2003-02-05 10:10:17 得分 5

我认为在现实中一定是用扫描算法，这个算法是比较简单的，而且实现的代码也不多，在现实中就是全扫描一次游戏屏幕也不会化太多时间，而且这个算法的空间占用是十分小的，在掌上机等小型设备中，这是一个优势。Top

7 楼ghost_117（ghost）回复于 2003-02-05 14:27:08 得分 5

可以考虑一下动态规划的思想，回溯法求全部的解确实不太现实。Top

8 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-02-05 17:13:25 得分 0

不能动态规划，没有最优子结构Top

9 楼nhzp（怒火之袍）回复于 2003-02-05 17:52:21 得分 0

最大不过6*6才9个方块
我觉得回溯还是可以接受的。Top

10 楼mmmcd（超超）回复于 2003-02-06 03:54:20 得分 0

能编出程序来吗？Top

11 楼sssxueren（xueren）回复于 2003-02-06 08:20:07 得分 5

俄罗斯方块，一共就只有那么几种，可以事先定义出来的，不需要考虑这么多的

至于旋转，就是种类变换而已

显示时候可以根据种类来显示具体的方块样式，很简单的Top

12 楼zhi_liu6（野战炮）回复于 2003-02-06 17:32:48 得分 0

怎么不能用动态规划？！Top

13 楼gladiatorcn（角斗士）回复于 2003-02-06 19:12:30 得分 5

完全可以使用回溯，这是一道很有趣的算法题。只要设计得当，很快的。贪心法可能都没有他快。
所谓的扫描算法？你理解错了。这可不是完成游戏。你说的到让我想起穷举法，暴力！其实也可以。哈哈！Top

14 楼snowrain（雪雨）回复于 2003-02-06 19:30:01 得分 5

听讲！Top

15 楼fly_dream0323（追蝴蝶的猪）回复于 2003-02-07 11:48:14 得分 5

你还没有登录：

Top

16 楼mmmcd（超超）回复于 2003-02-08 12:16:49 得分 0

是不是必须设二维数组[6][6]
初始全为零，放了方块部分为1，回溯时，方块挨个放、拿...Top

17 楼xingzhiyun（八宝齐）回复于 2003-02-09 12:53:13 得分 5

方块下降时,
先把自己的图行清除掉,
然后再探测下面的位置是否可以放置本方块,可以则在下边的位置上绘制自己
可以使用一个2维数组来表示网格,方块可以用一个字节的16位来表示
我开发过2个俄罗斯方块游戏,TC的和VB.net的,用的就是这种方法Top

18 楼xingzhiyun（八宝齐）回复于 2003-02-09 12:55:06 得分 5

俄罗斯方块算不上什么高深的算法,用普通的思维就可以完成,
要想练习智能算法可以考虑五子棋的下棋算法Top

19 楼Strong221（Strong）回复于 2003-02-09 16:24:09 得分 5

直接用a(i,j)
i=4,j=4来计算比较快！Top

20 楼zzwu（未名）回复于 2003-02-09 18:09:17 得分 5

长宽不大于6的矩形个数极有限,一一加以考虑就是了.Top

21 楼mmmcd（超超）回复于 2003-02-10 17:13:14 得分 0

这是《算法设计与分析》课后习题（电子工业出版社）
也是某年欧洲acm/icpc赛题Top

22 楼youngfighter（战士）回复于 2003-02-11 09:35:23 得分 5

markTop

23 楼victorxiang（维克厢）回复于 2003-02-11 09:45:39 得分 5

讨论的还可以啊！
不过，大家可以再具体些！Top

24 楼zalyer（小照）回复于 2003-02-11 23:37:10 得分 5

我有一份俄罗斯的源代,但是看不懂.Top

25 楼GramGramGram（）回复于 2003-02-14 14:42:58 得分 5

思想并不难，但代码的优化却很值得思考，大家有什么好方法能够减少回溯的次数吗？Top

26 楼kwest（为了Job，不得不学Linux）回复于 2003-02-15 23:40:03 得分 0

矩形长宽不大于6
这就要看矩形长、宽是奇偶组合了
要保证矩形面积是偶数才可能被上面的方块覆盖
至于用搜索来做，我想可以这样理解：
**** * * ** ** **
*** *** ** ** **

*
可以看作是 ** 和 * 两种形态把整个矩形铺满后相临两块间的组合数并且这种组合要保证不存在‘剩余’（即存在**或*为不能再组合的情况）
*
具体编程我也没想好
若哪位有原代码的不妨贡献出来吧！！
Top

27 楼hellowithsmile（张三^_^江南小百姓+抵制日货）回复于 2003-02-19 18:12:30 得分 5

3*3的矩阵就可以。
这是我写的
源码这里下载
http://www.vckbase.com/code/downcode.asp?id=1679Top

28 楼hellowithsmile（张三^_^江南小百姓+抵制日货）回复于 2003-02-19 18:14:08 得分 0

这是一个小巧的俄罗斯方块游戏源代码，
做的比较简单，主要是为了体现算法和分析思路。
很详细的注释和很清晰的编码风格，是初学者学习的好范例Top

29 楼mmmcd（超超）回复于 2003-03-02 09:18:37 得分 0

这里不是问俄罗斯方块游戏,这里只是想讨论回溯法Top

30 楼mmmcd（超超）回复于 2003-03-15 16:12:27 得分 0

Come on!!Top

31 楼mmmcd（超超）回复于 2003-03-25 16:06:37 得分 0

Any more??Top

32 楼zhouhu（阿虎）回复于 2003-03-26 11:37:44 得分 0

come onTop

33 楼fangrk（加把油，伙计！）回复于 2003-03-28 14:50:28 得分 5

/*Borland C++ 3.1
stone.cpp
使用stone.cpp时候，要把Egavga.bgi拷贝到stone.cpp的目录下，
打开Option/Linker/Libraries/Graphics library。
方向键“上”是旋转方块。
“下、左、右”是移动方块，若先按下“Shift”则加速。“Esc”退出。
若程序非正常结束，建议重新启动计算机！
*/
#include <graphics.h>
#include <iostream.h>
#include <conio.h>
#include <bios.h>
#include <stdlib.h>
#include <time.h>
#include <dos.h>

int count,board[20][10];
const int Timer=0x1c,ESC=0x11b,ENTER=0x1c0d,//Timer是系统时钟向量
UP=0x4800,DOWN=0x5000,LEFT=0x4b00,RIGHT=0x4d00;
void main()
{ int driver,mode,errorCode;
driver=DETECT;
mode=0;
initgraph(&driver,&mode,"");
// registerbigfont(gothic_font);
errorCode=graphresult();
if(errorCode){
cerr<<"Initgraph Failed!"<<endl;
return;
}
//5410可以通过analyze()分解为5,4,1,0，在4*4的方格中表示一个正方形
const int shape[19]={5410,//正方形
12840,3210,//长条
6542,9840,4210,9510,//9840:L形状
6210,9851,6540,8410,
5421,9540,
6510,8541,
6541,8540,5210,9541//5210:T形状
};

int key,start,end,index,randNum,boardX,boardY,screenX,screenY,score;
int speed,TboardX,TboardY,Tindex,sign,shiftPressed,t;
setcolor(LIGHTGRAY);
randomize();
setNewVect();

for(;;){
cleardevice();
setbkcolor(BLACK);
prepare();
score=0;
speed=18;
gotoxy(1,1);
delline();
cout<<"Your score is: "<<score*10<<endl;
while(1){
randNum=random(7);
switch(randNum)
{case 0:start=end=0;break;
case 1:start=1;end=2;break;
case 2:start=3;end=6;break;
case 3:start=7;end=10;break;
case 4:start=11;end=12;break;
case 5:start=13;end=14;break;
case 6:start=15;end=18;
}//switch 获取翻转时索引的首尾值
index=start+random(end-start+1);

boardX=0;boardY=4;
sign=afterChange(boardX,boardY,shape[index],DOWN);
screenX=boardY*10+200;screenY=boardX*10+100;//面板坐标转换到屏幕坐标
if(sign==2) {//生成图形时就冲突，游戏结束
drawShape(screenX,screenY,shape[index],RED);
break;
}
drawShape(screenX,screenY,shape[index],YELLOW);
count=0;
while(2){
key=0;
if(bioskey(1)) {
key=bioskey(0);
t=bioskey(2);
shiftPressed=(t==0x21||t==0x22?1:0);//判断是否同时按下了Shift
}
if(key==ESC) break;//Esc退出
if(count>speed){//大于设定值，图形就自动下降
if(key==0) shiftPressed=0;
key=DOWN;
count=0;
}
if(key==UP||key==DOWN||key==LEFT||key==RIGHT){
TboardX=boardX;//保存现在的坐标以及索引
TboardY=boardY;
Tindex=index;
switch(key)
{case UP: index=(index==end?start:index+1);break;//获得翻转后的索引
case DOWN: if(shiftPressed) {//获得该图形可以下降到的最大面板x坐标
for(t=boardX+1;t<=19;t++)
if(afterChange(t,boardY,shape[index],key)==3)
boardX=t;
else break;
}
else boardX++;
break;
case LEFT: if(shiftPressed){
for(t=boardY-1;t>=0;t--)
if(afterChange(boardX,t,shape[index],key)==3)
boardY=t;
else break;
}
else boardY--;
break;
case RIGHT:if(shiftPressed){
for(t=boardY+1;t<=9;t++)
if(afterChange(boardX,t,shape[index],key)==3)
boardY=t;
else break;
}
else boardY++;
}//switch
//判断新的图形、坐标的可行性
sign=afterChange(boardX,boardY,shape[index],key);
switch(sign)
{case 1:boardX=TboardX;//左右占位或者左右越界
boardY=TboardY;//恢复原来坐标
index=Tindex;
break;
case 2:boardX=TboardX;//下占位或者下越界
boardY=TboardY;//恢复
index=Tindex;
fillBoard(boardX,boardY,shape[index]);//写面板，表示以占用
//获得可以删除的行数，显示删除后的样子
t=deleteRow(boardX,shape[index]);
if(t){
gotoxy(1,1); delline();
switch(t){
case 1:++score;break;
case 2:score+=3;break;
case 3:score+=5;break;
case 4:score+=8;
}
cout<<"Your score is: "<<score*10<<endl;
//到达一定数值后，自动下降速度加快
//最快一秒钟自动下降六格(speed==3)，呵呵，挡得住吗？
speed=(18-score/10>3?18-score/10:3);
}
break;
case 3:screenX=TboardY*10+200;screenY=TboardX*10+100;//消除旧的图形
drawShape(screenX,screenY,shape[Tindex],BLACK);
screenX=boardY*10+200;screenY=boardX*10+100;//画新的图形
drawShape(screenX,screenY,shape[index],YELLOW);
}
if(sign==2) break;
}//if(key==UP||key==DOWN||key=LEFT||key==RIGHT)
}//while(2)
if(key==ESC) break;
}//while(1)
gotoxy(1,2); delline();
cout<<"Press Esc to quit or Enter to replay!"<<endl;
key=bioskey(0);//重新开始或者结束
while(key!=ESC&&key!=ENTER) key=bioskey(0);
if(key==ESC) break;
}//for(;;)
recoverOldVect();//恢复系统时钟中断向量
closegraph();
}Top

34 楼fangrk（加把油，伙计！）回复于 2003-03-28 14:50:58 得分 0

void analyze(int shapeNum,int (*result)[2])//把shapeNum分解为四对坐标
{ int i,t;
for(i=0;i<3;i++){
t=shapeNum%10;
shapeNum/=10;
(*result)[0]=t/4;
(*result)[1]=t%4;
result++;
}
(*result)[0]=shapeNum/4;
(*result)[1]=shapeNum%4;
}
void drawShape(int screenX,int screenY,int shapeNum,int fillColor)//不用说了吧
{ int i,temp[4][2];
analyze(shapeNum,temp);
setfillstyle(SOLID_FILL,fillColor);
for(i=0;i<4;i++)
bar(screenX+temp[i][1]*10+1,screenY+temp[i][0]*10+1,
screenX+temp[i][1]*10+9,screenY+temp[i][0]*10+9);
}
void prepare()//画线条，清除面板标志
{ int i,j;
for(i=200;i<=300;i+=10) line(i,100,i,300);
for(i=100;i<=300;i+=10) line(200,i,300,i);
for(i=0;i<20;i++)
for(j=0;j<10;j++) board[i][j]=0;
}
void interrupt newHandle(...)//新的向量入口
{ count++;
oldHandle();
}
void setNewVect()
{ oldHandle=getvect(Timer);//把系统时钟向量入口保存在oldHandle函数中
disable();
setvect(Timer,newHandle);//系统时钟向量的新函数
enable();
}
void recoverOldVect()
{ disable();
setvect(Timer,oldHandle);//恢复原来的系统时钟向量入口
enable();
}
//判断以(boardX,boardY)的shapeNum的合理性
int afterChange(int boardX,int boardY,int shapeNum,int key)
{ int temp[4][2],i,num,tt;
analyze(shapeNum,temp);
for(i=0;i<4;i++){
if(boardY+temp[i][1]<0||boardY+temp[i][1]>9) return 1;//左右越界
if(board[boardX+temp[i][0]][boardY+temp[i][1]]&&key!=DOWN) return 1;//左右占位
}
for(i=0;i<4;i++){//下越界或者下占位
tt=boardX+temp[i][0];
if(tt>19||board[tt][boardY+temp[i][1]]&&key==DOWN)
return 2;
}
return 3;//可以变换
}
int deleteRow(int boardX,int shapeNum)
{ int temp[4][2],deletedRows=0,i,j,top,bottom,row,screenX,screenY;
top=bottom=boardX;
analyze(shapeNum,temp);
for(i=0;i<4;i++)//top和bottom确定检测删除的范围，最多四行
if(bottom<temp[i][0]+top) bottom=temp[i][0]+top;
for(row=bottom;row>=top;){
if(rowFull(row)){
deletedRows++;
for(i=row;i>0;i--){
for(j=0;j<10;j++){//把第i-1行拷贝到第i行
if(board[i][j]!=board[i-1][j]){//如果上下相同，就不必消除了
screenX=j*10+200;screenY=i*10+100;
if(board[i-1][j])
setfillstyle(SOLID_FILL,YELLOW);
else setfillstyle(SOLID_FILL,BLACK);
bar(screenX+1,screenY+1,screenX+9,screenY+9);
board[i][j]=board[i-1][j];
}
}
}
}
else row--;
}
return deletedRows;
}

int rowFull(int row)//第row行是否已经满了
{ for(int i=0;i<10;i++)
if(board[row][i]==0) return 0;
return 1;
}
void fillBoard(int boardX,int boardY,int shapeNum)//填充面板
{ int temp[4][2],i;
analyze(shapeNum,temp);
for(i=0;i<4;i++) board[boardX+temp[i][0]][boardY+temp[i][1]]=1;
}Top