[数据结构与算法] 2021山东省赛 M - Matrix Problem 看样例+构造

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2021山东省赛 M - Matrix Problem 看样例+构造 -> 正文阅读

[数据结构与算法]2021山东省赛 M - Matrix Problem 看样例+构造

原题
在这里插入图片描述

输入：

输出：

题意：给只有01的矩阵C，求矩阵A、B。其中C中是1的地方A、B一定都要是1，反之亦然，且A，B中的1要能上下左右直接连通。
注意：C的最外一圈都是0.

刚看题的时候想太复杂了，以为是找什么最小的连通块(?)，实际上直接构造即可。

题解：用C初始化A、B，然后按照题目给的样例构造。可以使得：AB都是1的地方C一定是1（初始化就是如此），且AB不会存在同时是1且C不是1的情况（构造的规则如此）。

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define ll long long
const int N=5e2+10;
int n,m;
char g[N][N],a[N][N],b[N][N];
int main()
{
	cin>>n>>m;
	fir(i,1,n)
	{
		fir(j,1,m)
		{
			cin>>g[i][j];
			a[i][j]=g[i][j];
			b[i][j]=g[i][j];
		}
	}
	
	//A
	fir(i,1,n)
	{
		if(i%2)//奇数
		{
			for(int j=1;j<=m-1;j++) a[i][j]='1';
		} 
		else //偶数
		{
			a[i][1]='1';
		} 
	}
	
	//B
	fir(i,1,n)
	{
		if(i%2==0)//偶数
		{
			for(int j=2;j<=m;j++) b[i][j]='1';
		} 
		else //奇数
		{
			b[i][m]='1';
		} 
	}
	
	fir(i,1,n)
	{
		fir(j,1,m)
		{
			cout<<a[i][j];
		}
		cout<<endl;
	}
	fir(i,1,n)
	{
		fir(j,1,m)
		{
			cout<<b[i][j];
		}
		cout<<endl;
	}
	return 0;
}