原文链接：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 }