CCF 俄罗斯方块 满分代码（有注释） + 解题思路（很简单直白的做法） + 技巧总结 201604 - 2

技巧总结

• 对于需要先判断可不可以再进行“填充”数组的操作，可以利用memcpy，在一个新的数组上“试错”
• 小数组在大数组中实现遍历，可以利用小数组的行列遍历，然后加上大数组的偏移量就可以遍历大数组
  
  

题目描述

解题思路

• 该题数据范围不大，只有两百年，可以采用暴力枚举来解题
• 从上而下枚举每一行，以（r, c)这个点作为小方块在大方块中的左上角位置，遍历小方块，看小方块会不会与大方块相重叠，第一次出现重叠的位置，就是刚好阻塞的地方，其上一行的状态就是答案，可以将上一行小方块在大方块中是1的位置记录在大方块中，输出大方块即是答案。
• 还有一个问题就是，可能会出现大方块最后一行没有没有1，或者小方块的下面几行也没有1，为了防止复杂的特判，只需要在大方块下面的第16行，17行，18行，19行全填充上1，就不需要额外判断板块在小方块中的位置情况，模拟自然下落即可。
  
  

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>using namespace std;int g[20][10];
int p[4][4];int main()
{memset(g, 1, sizeof(g)); //会使16行及以下是1，避免特判边界的问题，板块碰界可以统一处理//输入大方块for (int i = 1; i <= 15; i ++){for (int j = 1; j <= 10; j ++){cin >> g[i][j];}}//输入小方块for (int i = 0; i < 4; i ++){for (int j = 0; j < 4; j ++){cin >> p[i][j];}}//输入开始的列数int c;cin >> c;for (int r = 1; ; r ++) //一定会碰壁，停止循环，所以不同设结束条件，从第1行开始，每次从（r,c)开始遍历小方块，模拟小方格下落的过程{bool st = false;for (int i = 0; i < 4; i ++){for (int j = 0; j < 4; j ++){if (p[i][j] && g[r + i][c + j]) //两者有重叠{st = true;break;}}if (st) break;}if (st) //如果出现了重叠，则说明答案应该是上一行的状态{r --; //返回上一行for (int i = 0; i < 4; i ++){for (int j = 0; j < 4; j ++){if (p[i][j]) g[r + i][c + j] = p[i][j]; //将小方块是1的地方填充在大方块中}}break;}}//输出最后的答案for (int i = 1; i <= 15; i ++){for (int j = 1; j <= 10; j ++){cout << g[i][j] << " ";}cout << endl;}return 0;
}