Educational Codeforces Round 71 (Rated for Div. 2) B - Square Filling

原文链接:https://www.cnblogs.com/xwl3109377858/p/11404261.html

Educational Codeforces Round 71 (Rated for Div. 2)

B - Square Filling

You are given two matrices A and B. Each matrix contains exactly n rows and m columns. Each element of A is either 0 or 1; each element of B is initially 0.

You may perform some operations with matrix B. During each operation, you choose any submatrix of B having size 2×2, and replace every element in the chosen submatrix with 1. In other words, you choose two integers x and y such that 1≤x<n and 1≤y<m, and then set Bx,y, Bx,y+1, Bx+1,y and Bx+1,y+1 to 1.

Your goal is to make matrix B equal to matrix A. Two matrices A and B are equal if and only if every element of matrix A is equal to the corresponding element of matrix B.

Is it possible to make these matrices equal? If it is, you have to come up with a sequence of operations that makes B equal to A. Note that you don't have to minimize the number of operations.

Input

The first line contains two integers n and m (2≤n,m≤50).

Then n lines follow, each containing m integers. The j-th integer in the i-th line is Ai,j. Each integer is either 0 or 1.

Output

If it is impossible to make B equal to A, print one integer −1.

Otherwise, print any sequence of operations that transforms B into A in the following format: the first line should contain one integer k — the number of operations, and then k lines should follow, each line containing two integers x and y for the corresponding operation (set Bx,y, Bx,y+1, Bx+1,y and Bx+1,y+1 to 1). The condition 0≤k≤2500 should hold.

Examples

input

3 3

1 1 1

1 1 1

0 1 1

output

3

1 1

1 2

2 2

input

3 3

1 0 1

1 0 1

0 0 0

output

-1

input

3 2

0 0

0 0

0 0

output

0

Note

The sequence of operations in the first example:

000       110        111        111

000  →  110  →    111  →  111

000       000        000       011

 

题意:题目意思是给你一个由0,1组成的矩阵和一个空白矩阵,

你可以对空白矩阵进行操作,选择一个点,为左上点,使其2*2矩阵被1覆盖,

问你能不能把空白矩阵变成所给矩阵。

思路:先根据原矩阵中的0,标记矩阵中不能改变的几个点(为2*2矩阵,该0点为右下点),

最后用1矩阵把没有标记的点覆盖,看两个矩阵是否一样。

 

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<map>
  7 #include<set>
  8 #include<vector>
  9 #include<queue>
 10 #include<stack>
 11 #include<list>
 12 //#include<unordered_map>
 13 using namespace std;
 14 #define ll long long 
 15 const int mod=1e9+7;
 16 const long long int inf=1e18+7;
 17 
 18 const int maxn=105;
 19 
 20 int a[maxn][maxn];
 21 
 22 int b[maxn][maxn];
 23 
 24 int book[maxn][maxn];
 25 
 26 int n,m;
 27 
 28 inline bool check(int x,int y)
 29 {
 30     if(x<1||x>n||y<1||y>m)
 31         return false;
 32     return true;
 33 }
 34 
 35 int main()
 36 {
 37     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 38     
 39     while(cin>>n>>m)
 40     {
 41         memset(a,0,sizeof(a));
 42         memset(b,0,sizeof(b));
 43         memset(book,0,sizeof(book));
 44         
 45         for(int i=1;i<=n;i++)
 46         {
 47             for(int j=1;j<=m;j++)
 48             {
 49                 cin>>a[i][j];
 50             }
 51         }
 52         
 53         for(int i=1;i<=n;i++)
 54         {
 55             for(int j=1;j<=m;j++)
 56             {
 57                 if(a[i][j]==0)
 58                 {
 59                     book[i][j]=1;//这个点不能动
 60                     
 61                     if(check(i-1,j-1))
 62                         book[i-1][j-1]=1;
 63                     if(check(i-1,j))
 64                         book[i-1][j]=1;
 65                     if(check(i,j-1))
 66                         book[i][j-1]=1;    
 67                 }
 68             }
 69         }
 70         vector<pair<int,int> >v;
 71         
 72         for(int i=1;i<n;i++)//取2*2矩阵,边界无法取 
 73         {
 74             for(int j=1;j<m;j++)
 75             {
 76                 if(book[i][j]==0)//可以动
 77                 {
 78                     v.push_back(make_pair(i,j));
 79                     b[i][j]=1;
 80                     b[i+1][j]=1;
 81                     b[i][j+1]=1;
 82                     b[i+1][j+1]=1;
 83                  } 
 84             }
 85         }
 86         
 87         int flag=0;
 88         
 89         for(int i=1;i<=n;i++)
 90         {
 91             for(int j=1;j<=m;j++)
 92             {
 93                 if(a[i][j]!=b[i][j])
 94                 {
 95                     flag=1;
 96                     break;
 97                 }
 98             }
 99         }
100         
101         if(flag)
102             cout<<-1<<endl;
103         else
104         {
105             cout<<v.size()<<endl;
106             for(int i=0;i<v.size();i++)
107                 cout<<v[i].first<<" "<<v[i].second<<endl;
108         }
109         
110     }
111     
112     return 0;
113 }

 

上一篇:C# Entity Framework The ObjectContext instance has been disposed and can no longer be used for opera


下一篇:Multiple Thread with dependencies