原文链接:https://www.cnblogs.com/xwl3109377858/p/11404261.html
Educational Codeforces Round 71 (Rated for Div. 2)
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 }