【洛谷入门6】函数与结构体 P5461 赦免战俘

阳光穿透心脏的1/2处 2022-10-29 06:27 103阅读 0赞

## P5461 赦免战俘 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]

输入输出样例
    输入 
    3
    输出 
    0 0 0 0 0 0 0 1
    0 0 0 0 0 0 1 1
    0 0 0 0 0 1 0 1
    0 0 0 0 1 1 1 1
    0 0 0 1 0 0 0 1
    0 0 1 1 0 0 1 1
    0 1 0 1 0 1 0 1
    1 1 1 1 1 1 1 1

**分治和递归的思想**

不难发现  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]  
所以，代码如下：

#include <bits/stdc++.h>
    using namespace std;
    int a[1025][1025]={
        0};  // 这里先让0表示不被赦免，1表示被赦免
    
    void fun(int x,int y,int l)  // x、y代表坐标，l代表边长，初始化边长为2的n次方
    {
        
    	if(l==1) return ;
    	for(int i=x;i<=x+l/2-1;i++)
    		for(int j=y;j<=y+l/2-1;j++)
    			a[i][j]=1;
    	
    	// 由上面的分析知道，继续求剩下区域被赦免的
    	// 前面两个参数代表起始坐标
    	fun(x,y+l/2,l/2);
    	fun(x+l/2,y,l/2);
    	fun(x+l/2,y+l/2,l/2);
    }
    
    int main()
    {
        
    	int n;
    	cin>>n;
    	int k=pow(2,n);
    	fun(1,1,k); // 开始递归
    	for(int i=1;i<=k;i++)
    	{
        
    		for(int j=1;j<=k;j++)
    		{
        
    			if(a[i][j]==0) cout<<"1 "; // 这里要相反输出，因为我们假设的跟题目要输出的刚好相反
    			else cout<<"0 ";	
    		} 
    		cout<<endl;
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/eaba685d74ed4e7b81fff344e9137c21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/40b2765618ad405a8883fd2f738dc1df.png