201604-2 俄罗斯方块

淩亂°似流年 2022-11-11 06:17 135阅读 0赞

## 解题思路 ##

对下降的方块确定上下左右界限，在地图中找到下降的起始列和结束列（和下降块匹配），遍历地图map，直到当前的位置的值和下降块该处的值相与，如果`=1`，说明找到了第一个可能是界限的行，然后从当前行进行遍历，遍历的方法是：

假如下降块为：
    0 1 1 0
    0 0 1 0
    0 0 1 0
    0 0 0 0
    分离之后的下降块为：
    1 1
    0 1
    0 1
    即只保留包含整个下降块的矩阵，然后用该矩阵去遍历分离出的map
    先从地图map中确认起始的列：n-1+left_boundary，结束列：n-1+right_boundary
    测试数据：
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 1 0 0 0
    1 1 1 1 0 0 1 1 1 1
    0 0 0 0 1 0 0 0 0 0
    0 1 1 0
    0 0 1 0
    0 0 1 0
    0 0 0 0
    3

裁剪后的map为：  
![测试样例1][1]  
遍历分离的map发现第一个可能在此停止下降的点：  
![测试样例2][2]  
用改行与下降块的最后一行进行匹配，如果不满足对应元素相与为1的情况，就将其增加为两行，与下降块的倒数两行进行判断  
【注意】数组map增设一行，即最后一行全设为1，防止下降过程中无障碍物数组下标访问越界的情况，同时便于判断。  
【说明】下降停留行位置的判断实例：

下降块：（此处新设的数据，与上例的数据不同）
    1 1
    0 1
    0 1
    遍历得到的第一个对应位置相与不为0的map的行：
    1 0
    用改行与最后一行：0 1匹配，0 && 1 = 0, 1 && 0 = 0，不满足条件，则方格可以继续下降一个单位，于是就变为：
    0 1
    0 1
    与map的 1 0及其下一行匹配，假设为
    1 0
    1 0
    按照以上方法，仍然不匹配，继续下降一个单位：
    1 1
    0 1
    0 1
    与
    1 0
    1 0
    1 0
    匹配，由于1 && 1 = 1，满足条件，得到降落点所在行，然后根据得到的行标记，用切割后的下降块矩阵更新map。

**经检查，该代码不完整，仍然存在bug…在中间的障碍物，无法正确检测。**

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    const int ROW = 15;
    const int COL = 10;
    const int N = 4;
    
    int map[ROW + 1][COL];
    int block[N][N];
    int lower_boundary = 0, upper_boundary = 3;
    int left_boundary = 3, right_boundary = 0;
    
    int main(int argc, char const *argv[])
    {
        
    	std::ios::sync_with_stdio(false);
    
    	for (int i = 0; i < ROW; i++)
    	{
        
    		for (int j = 0; j < COL; j++)
    		{
        
    			cin >> map[i][j];
    		}
    	}
    	for (int j = 0; j < COL; j++)
    	{
        
    		map[ROW][j] = 1;
    	}
    
    	for (int i = 0; i < N; i++)
    	{
        
    		for (int j = 0; j < N; j++)
    		{
        
    			cin >> block[i][j];
    			if (block[i][j])
    			{
        
    				if (i < upper_boundary)
    					upper_boundary = i;
    				if (i > lower_boundary)
    					lower_boundary = i;
    				if (j < left_boundary)
    					left_boundary = j;
    				if (j > right_boundary)
    					right_boundary = j;
    			}
    		}
    	}
    	// printf("upper_boundary:%d\n", upper_boundary);
    	// printf("lower_boundary:%d\n", lower_boundary);
    	// printf("left_boundary:%d\n", left_boundary);
    	// printf("right_boundary:%d\n", right_boundary);
    	int n;
    	cin >> n; // 从左边的第n-1列开始下落
    
    	// 找到第一个不为0的障碍物节点
    	int flag_x = ROW;
    	bool flag = false;
    	// cout << n - 1 + left_boundary << endl;
    	// cout << n + right_boundary + 1 << endl;
    	for (int i = 0; i < ROW + 1 && !flag; i++)
    	{
        
    		for (int j = n - 1 + left_boundary; j < n + right_boundary; j++)
    		{
        
    			// 如果该位置不为0
    			if (map[i][j])
    			{
        
    				flag_x = i;
    				flag = true;
    				break;
    			}
    		}
    	}
    	// printf("flag_x=%d\n", flag_x);
    	flag = false;
    	int stop_x = flag_x;
    	for (int i = lower_boundary, index = 0; i >= upper_boundary - index && !flag; i--)
    	{
        
    		for (int j = left_boundary; j <= right_boundary; j++)
    		{
        
    			if (block[i][j] && map[flag_x + index][n - 1 + j])
    			{
        
    				stop_x = flag_x + index;
    				flag = true;
    				break;
    			}
    		}
    		if (!flag)
    		{
        
    			index++;
    		}
    	}
    	// printf("stop_x=%d\n", stop_x);
    
    	// 更新格子状态
    	int start_x = stop_x - 1;
    	for (int i = lower_boundary; i >= upper_boundary; i--, start_x--)
    	{
        
    		int start_y = n - 1 + left_boundary;
    		for (int j = left_boundary; j <= right_boundary; j++, start_y++)
    		{
        
    			map[start_x][start_y] = map[start_x][start_y] || block[i][j];
    		}
    	}
    
    	// output
    	for (int i = 0; i < ROW; i++)
    	{
        
    		for (int j = 0; j < COL; j++)
    		{
        
    			cout << map[i][j] << " ";
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

### 修改版 ###

> 参考：[https://blog.csdn.net/tigerisland45/article/details/54790942][https_blog.csdn.net_tigerisland45_article_details_54790942]

主要思想在于构建下降的坐标系，下降块（`4*4`的矩阵）`block`左上角为坐标原点，每次遍历将坐标原点下移一个单位，直到满足可以停落的条件，然后用之前标记的`block`中为`1`的障碍物的坐标去填充背景图`backmap`即可。

#include <iostream>
    using namespace std;
    
    const int ROW = 15;
    const int COL = 10;
    const int N = 4;
    int backmap[ROW + 1][COL];
    int block[N][N];
    
    struct coord
    {
        
        int row;
        int col;
    
        void operator()(const int row, const int col)
        {
        
            this->row = row;
            this->col = col;
        }
    } coords[N];
    
    int main(int argc, char const *argv[])
    {
        
        std::ios::sync_with_stdio(false);
        int row, col;
    
        // 初始化
        for (int i = 0; i < ROW; i++)
        {
        
            for (int j = 0; j < COL; j++)
            {
        
                cin >> backmap[i][j];
            }
        }
        for (int i = 0; i < N; i++)
        {
        
            for (int j = 0; j < N; j++)
            {
        
                cin >> block[i][j];
            }
        }
        cin >> col;
        for (int j = 0; j < COL; j++)
        {
        
            backmap[ROW][j] = 1; // 将最后一行设置为1
        }
        // 记录block的不为0的障碍块的相对坐标
        int k = 0;
        for (int i = N - 1; i >= 0; i--)
        {
        
            for (int j = 0; j < N; j++)
            {
        
                if (block[i][j])
                {
        
                    coords[k++](i, j);
                }
            }
        }
        for (int i = 0; i < N; i++)
        {
        
            cout << coords[i].row << "," << coords[i].col << endl;
        }
    
        // 处理下降
        row = 1, col--;
        bool flag = false;
        while (!flag)
        {
        
            for (int i = 0; i < N; i++)
            {
        
                if (backmap[row + coords[i].row][col + coords[i].col] == 1)
                {
        
                    flag = true;
                    break;
                }
            }
            if (!flag)
                row++;
            else
                break;
        }
        row--; // 得到满足降落的坐标
        for (int i = 0; i < N; i++)
        {
        
            backmap[row + coords[i].row][col + coords[i].col] = 1;
        }
        for (int i = 0; i < ROW; i++)
        {
        
            for (int j = 0; j < COL; j++)
            {
        
                cout << backmap[i][j] << " ";
            }
            cout << endl;
        }
    
        return 0;
    }

【PS】使用两个`break`的原因：`break`只能够一层一层地跳出循环，不能跳出多重循环，如果要直接跳出多重循环，需要使用`goto`语句，但并不推荐使用，`goto`破坏了代码的结构。

[1]: /images/20221022/6fab27935f5b4d8299f619ea09d68bc5.png
[2]: /images/20221022/0588f48f97cf4765a86d53ab7354059d.png
[https_blog.csdn.net_tigerisland45_article_details_54790942]: https://blog.csdn.net/tigerisland45/article/details/54790942