2021山东省赛 M . Matrix Problem(构造)-阿里云开发者社区

2021山东省赛 M . Matrix Problem(构造)

2023-07-11 93

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 2021山东省赛 M . Matrix Problem(构造)

描述：

A teacher gives his students a problem to test his students’ construction skills.

The teacher has two 0/1 matrices A and B with n rows and m columns, where all the 1 of both matrices separately form a 4-connected block. 4-connected means that each cell is connected with adjacent cells in four directions (up, down, leftward and rightward).

Now the teacher gives a third matrix C with n rows and m columns, and a specifific position of this matrix is 1 if and only if the corresponding positions of the two matrices are 1.

You need to fifind two matrices A and B such that one of the positions of C is 1 if and only if the corresponding positions of A,B are both 1.

输入：

The first line contains two integers n and m (3≤n,m≤500) – the size of the matrices.

The next n lines describe the matrix C. Each of the following n lines contains m characters 0 or 1.

It is guaranteed that the boundaries of the matrix C are 0, i.e., the 1-st row, the 1-st column, the n-th row and the m-th column of the matrix C are 0.

输出：

Print 2n lines and each line has m characters 0 or 1.

The first n lines describe the matrix A.

The next n lines describe the matrix B.

If there are multiple answers, print any of them.

样例输入：

样例输出；

大意：

给出一个矩阵，为C矩阵，保证C矩阵的边界元素为 0，C矩阵由AB两个矩阵得来，AB矩阵中相同位置都是1 C矩阵中为1，否则C矩阵中元素为 0，AB矩阵中的所有1连通(上下左右四个方向)，给出C矩阵，求出AB矩阵；

思路：

构造连通矩阵

首先在C矩阵中的‘1’在AB矩阵中也是‘1’，这时毋庸置疑的，其次我们尝试构造A矩阵的所有奇数行都是‘1’，B矩阵的所有偶数行都是‘1’，这样既不会对C矩阵产生影响(0,1结合为0)，又能最大程度上保持连通,(注意不要动边界元素，只处理AB中非边界元素，一会给出原因)；

但是这样构造是存在缺陷的，我们给出一组例子

按照我们刚才的构造方法，AB矩阵分别为

我们可以明显的看出来B矩阵是不连通的，这时候怎么解决这个问题呢，就要用的我们没处理的边界元素了，我们让A矩阵的第一列全为1，B矩阵的最后一列全为1(反过来也可)，就能完美的解决连通问题，也不会影响C矩阵的元素；

构造后的序列

这时候处理完了，还有最后一个问题，就是一开始为什么不处理边界元素，这是因为假如在AB奇偶行处理的时候把边界元素都处理了，第二次处理第一列和最后一列的时候必定会在边界出现两个矩阵都是‘1’的情况，但是我们C矩阵边界不能有‘1’，因此第一次处理的时候避开边界(必须是第一次处理避开边界)；

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 2*1e5+100;
const int p = 1e4;
const double eps = 1e-8;
int n,m;
string s[501];
int main()
{
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>s[i];
  }
  //A矩阵 
  printf("1"); 
  for(int i=2;i<=m;i++) printf("0");
  printf("\n");//A第一行
  for(int i=2;i<=n-1;i++)
  {
    printf("1");
    for(int j=1;j<s[i].size()-1;j++)
    {
      if(s[i][j]=='1') printf("1");
      if(s[i][j]=='0')
      {
        if(i%2!=0)
          printf("1");
        else
          printf("0");  
      } 
    }
    printf("0\n");
  }//A中间行
  printf("1"); 
  for(int i=2;i<=m;i++) printf("0");
  printf("\n");//A末行
  for(int i=1;i<m;i++) printf("0");
  printf("1");
  printf("\n");//B第一行
  for(int i=2;i<=n-1;i++)
  {
    printf("0");
    for(int j=1;j<s[i].size()-1;j++)
    {
      if(s[i][j]=='1') printf("1");
      if(s[i][j]=='0')
      {
        if(i%2==0)
          printf("1");
        else
          printf("0");  
      } 
    }
    printf("1\n");
  }//B中间行
  for(int i=1;i<m;i++) printf("0");
  printf("1");
  printf("\n");//B末行
}