http://acm.hdu.edu.cn/showproblem.php?pid=3013
先发泄一下，这道题写了24+小时，太恶心了..感谢黑大的一个童鞋挑出了我思路的bugO(∩_∩)O~~看着他9000B+的代码开始羡慕后来..hiahia~~3000B+搞定~~
| 8229075 | 2013-05-04 00:12:03 | Accepted | 3013 | 0MS | 332K | 3788 B | G++ | Dream |
| 8229071 | 2013-05-04 00:10:42 | Presentation Error | 3013 | 0MS | 328K | 3790 B | G++ | Dream |
| 8229069 | 2013-05-04 00:10:39 | Compilation Error | 3013 | 0MS | 0K | 931 B | G++ | Dream |
| 8229065 | 2013-05-04 00:10:02 | Presentation Error | 3013 | 0MS | 328K | 3790 B | G++ | Dream |
| 8228963 | 2013-05-03 23:45:21 | Wrong Answer | 3013 | 0MS | 328K | 3791 B | G++ | Dream |
| 8228891 | 2013-05-03 23:35:36 | Wrong Answer | 3013 | 0MS | 328K | 3881 B | G++ | Dream |
| 8221926 | 2013-05-03 07:52:24 | Wrong Answer | 3013 | 0MS | 328K | 3258 B | G++ | Dream |
| 8221231 | 2013-05-02 22:43:47 | Wrong Answer | 3013 | 0MS | 328K | 3243 B | G++ | Dream |
好吧~~先兴奋一下
解题思路：
一共有7种形状的方块，每种4个角度，4个单位，每个单位用二维相对坐标表示出来，dir[][][][]数组
对于每一块下落后从下到上找到安全点，试着下落状态map[][]然后进行消除。如果没有越界的state[][]更新；
注意：**假设块7下落发生越界，但是可以将某一行消除掉，更新后的状态没有越界的，那么继续下落方块
代码如下：
View Code
#include <stdio.h> #include <cstring> #include <iostream> using namespace std; int dir[7][4][4][2]={ {{{0, 0}, {0, 1}, {0, 2}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}}, {{0, 0}, {0, 1}, {0, 2}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}}}, {{{0, 0}, {0, 1}, {0, 2}, {1, 0}}, {{0, 0}, {1, 0}, {2, 0}, {2, 1}}, {{0, 0}, {0, 1}, {0, 2}, {-1, 2}}, {{0, 0}, {0, 1}, {1, 1}, {2, 1}}}, {{{0, 0}, {0, 1}, {0, 2}, {1, 2}}, {{0, 0}, {0, 1}, {1, 0}, {2, 0}}, {{0, 0}, {1, 0}, {1, 1}, {1, 2}}, {{0, 0}, {0, 1}, {-1, 1}, {-2, 1}}}, {{{0, 0}, {0, 1}, {1, 0}, {1, 1}}, {{0, 0}, {0, 1}, {1, 0}, {1, 1}}, {{0, 0}, {0, 1}, {1, 0}, {1, 1}}, {{0, 0}, {0, 1}, {1, 0}, {1, 1}}}, {{{0, 0}, {0, 1}, {1, 1}, {1, 2}}, {{0, 0}, {1, 0}, {0, 1}, {-1, 1}}, {{0, 0}, {0, 1}, {1, 1}, {1, 2}}, {{0, 0}, {1, 0}, {0, 1}, {-1, 1}}}, {{{0, 0}, {0, 1}, {0, 2}, {1, 1}}, {{0, 0}, {1, 0}, {2, 0}, {1, 1}}, {{0, 0}, {0, 1}, {0, 2}, {-1, 1}}, {{0, 0}, {0, 1}, {-1, 1}, {1, 1}}}, {{{0, 0}, {0, 1}, {-1, 1}, {-1, 2}}, {{0, 0}, {1, 0}, {1, 1}, {2, 1}}, {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}}, {{0, 0}, {1, 0}, {1, 1}, {2, 1}}} }; //7种形状4种度数4个点的相对x,y坐标 int map[30][15]; //记录下落后的状态 int state[30][15]; //记录前状态 int sum[30]; //标记改行有多少个空格被占据 int safe(int x, int y) { if(x>0&&y>0&&y<=10&&map[x][y]==0) return 1; return 0; } int main() { int m, id, de, pos, i, j, k, x1, y1, x2, y2, x3, y3, x4, y4, jj; int frx1, frx2, frx3, frx4, fry1, fry2, fry3, fry4; while(scanf("%d", &m)!=EOF) { memset(map, 0, sizeof(map)); memset(sum, 0, sizeof(sum)); memset(state, 0, sizeof(state)); int flag=0; //标记最终是否能赢 for(i=0; i<m; i++) { scanf("%d%d%d", &id, &de, &pos); if(flag==1) continue; id--; de/=90; for(j=23; j>0; j--) //从上往下找 { x1=j+dir[id][de][0][0], y1=pos+dir[id][de][0][1]; x2=j+dir[id][de][1][0], y2=pos+dir[id][de][1][1]; x3=j+dir[id][de][2][0], y3=pos+dir[id][de][2][1]; x4=j+dir[id][de][3][0], y4=pos+dir[id][de][3][1]; if(safe(x1, y1)&&safe(x2, y2)&&safe(x3, y3)&&safe(x4, y4)) { frx1=x1, frx2=x2, frx3=x3, frx4=x4; fry1=y1, fry2=y2, fry3=y3, fry4=y4; } else break; } if(j==23) flag=1; if(flag) continue; map[frx1][fry1]=1, map[frx2][fry2]=1, map[frx3][fry3]=1, map[frx4][fry4]=1; sum[frx1]++, sum[frx2]++, sum[frx3]++, sum[frx4]++; for(j=1; j<=20; j++) { while(sum[j]==10) //改行被占据，消除改行 以上的行平移下来 { for(jj=j+1; jj<25; jj++) { for(k=1; k<=10; k++) map[jj-1][k]=map[jj][k]; sum[jj-1]=sum[jj]; } } } for(j=21; j<25; j++) if(sum[j]) flag=1;//消除后存在越界情况，游戏结束 if(flag!=1) { for(j=0; j<=20; j++) for(jj=0; jj<=10; jj++) state[j][jj]=map[j][jj]; } } printf("+--------------------+\n"); for(i=20; i>=1; i--) { printf("|"); for(j=1; j<=10; j++) { if(state[i][j]==1) printf("[]"); else printf(".."); } printf("|\n"); } printf("+--------------------+\n\n"); } return 0; }