[暴力] Educational Codeforces Round 71 (Rated for Div. 2) B. Square Filling (1207B)

题目:http://codeforces.com/contest/1207/problem/B

B. Square Filling

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Copy

Output

Copy

Input

Copy

Output

Copy

-1

Input

Copy

Output

Copy

Note

The sequence of operations in the first example:

000000000→110110000→110110110→110111111

题意:

给两个n*m的01矩阵A和B,给出了A中的元素，B中元素全为０，现在有一个操作可以在B中选一个坐标，它和右边下面右下的元素都变为１，问能否通过一些操作（不要求最少）使得B等于A，若能则输出步数和坐标，否则输出-１

思路:

暴力并判断边界(当时忘记判断边界结果被Hack了 ~TAT~ )

 #include<bits/stdc++.h>

 using namespace std;

 const int amn=;

 int a[amn][amn],idx[amn][amn],ansx[],ansy[];

 int main(){

     int n,m,tp=,valid=;

     cin>>n>>m;

     for(int i=;i<=n;i++){

         for(int j=;j<=m;j++){

             cin>>a[i][j];

             idx[i][j]=;

         }

     }

     for(int i=;i<=n;i++){

         for(int j=;j<=m;j++){

             if(a[i][j]){

                 if(!idx[i][j]&&(i+>n||j+>m)){ ///这里判断边界条件被hack了...当时想着i<n&&j<m,判非法时忘记判边界了

                     valid=0;

                     break;

                 }

                 if(a[i][j+]&&a[i+][j]&&a[i+][j+]){

                     idx[i][j+]=idx[i+][j]=idx[i+][j+]=;

                     ansx[++tp]=i;ansy[tp]=j;

                 }

                 else if(!idx[i][j]&&(!idx[i][j+]||!idx[i+][j]||!idx[i+][j+])){

                     valid=;

                     break;

                 }

             }

         }

         if(valid==)break;

     }

     if(valid){

         cout<<tp<<endl;

         for(int i=;i<=tp;i++)cout<<ansx[i]<<' '<<ansy[i]<<endl;

     }

     else cout<<-<<endl;

 }

 /**

 给两个n*m的01矩阵A和B,给出了A中的元素，B中元素全为０，现在有一个操作可以在B中选一个坐标，它和右边下面右下的元素都变为１，问能否通过一些操作（不要求最少）使得B等于A，若能则输出步数和坐标，否则输出-１

 暴力并判断边界

 **/

巴特西

[暴力] Educational Codeforces Round 71 (Rated for Div. 2) B. Square Filling (1207B)

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

. 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

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

equal to A

and m (2≤n,m≤50

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

equal to A, print one integer −1

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

题意:

给两个n*m的01矩阵A和B,给出了A中的元素，B中元素全为０，现在有一个操作可以在B中选一个坐标，它和右边下面右下的元素都变为１，问能否通过一些操作（不要求最少）使得B等于A，若能则输出步数和坐标，否则输出-１

思路:

暴力并判断边界(当时忘记判断边界结果被Hack了 ~TAT~ )

最新文章

热门文章