B. Square Filling
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two matrices ? and ?. Each matrix contains exactly ? rows and ? columns. Each element of ? is either 0 or 1; each element of ? is initially 0.
You may perform some operations with matrix ?. During each operation, you choose any submatrix of ? having size 2×2, and replace every element in the chosen submatrix with 1. In other words, you choose two integers ? and ? such that 1≤?<? and 1≤?<?, and then set ??,?, ??,?+1, ??+1,? and ??+1,?+1 to 1.
Your goal is to make matrix ? equal to matrix ?. Two matrices ? and ? are equal if and only if every element of matrix ? is equal to the corresponding element of matrix ?.
Is it possible to make these matrices equal? If it is, you have to come up with a sequence of operations that makes ? equal to ?. Note that you don’t have to minimize the number of operations.
Input
The first line contains two integers ? and ? (2≤?,?≤50).
Then ? lines follow, each containing ? integers. The ?-th integer in the ?-th line is ??,?. Each integer is either 0 or 1.
Output
If it is impossible to make ? equal to ?, print one integer −1.
Otherwise, print any sequence of operations that transforms ? into ? in the following format: the first line should contain one integer ? — the number of operations, and then ? lines should follow, each line containing two integers ? and ? for the corresponding operation (set ??,?, ??,?+1, ??+1,? and ??+1,?+1 to 1). The condition 0≤?≤2500 should hold.
Examples
inputCopy
3 3
1 1 1
1 1 1
0 1 1
outputCopy
3
1 1
1 2
2 2
inputCopy
3 3
1 0 1
1 0 1
0 0 0
outputCopy
-1
inputCopy
3 2
0 0
0 0
0 0
outputCopy
0
Note
The sequence of operations in the first example:
000000000→110110000→110110110→110111111
题意： 二维矩阵a,b。a矩阵全是0，你每次可以在a里面指定一个2x2的矩阵全部赋为1。问能否使得a矩阵等于b矩阵
思路： 这题出了好几次了。。。
只需要贪心的选择b里面的2x2矩阵，记录下位置，在a里面相同位置染色为1。最后比对一下a和b矩阵即可。
#include <cstdio>
#include <algorithm>
#include <vector>using namespace std;
const int maxn = 1e6 + 7;int a[55][55],b[55][55];
int vis[55][55];
vector<pair<int,int> >ans;int main()
{int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){scanf("%d",&a[i][j]);}}for(int i = 1;i < n;i++){for(int j = 1;j < m;j++){if(a[i + 1][j + 1] == 1 && a[i][j] == 1 && a[i + 1][j] == 1 && a[i][j + 1] == 1){ans.push_back(make_pair(i,j));}}}for(int i = 0;i < ans.size();i++){int x = ans[i].first;int y = ans[i].second;b[x][y] = 1;b[x + 1][y + 1] = 1;b[x + 1][y] = 1;b[x][y + 1] = 1;}for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){if(b[i][j] != a[i][j]){printf("-1\n");return 0;}}}printf("%d\n",ans.size());for(int i = 0;i < ans.size();i++){printf("%d %d\n",ans[i].first,ans[i].second);}return 0;
}