题解 CF1207B 【Square Filling】

发表于 更新于 阅读次数： Waline：
CF1207B 【Square Filling】题解。

这个题实际上就是裸的暴力……然而我仍然在WA了3次，有一次还是样例WA了

思路：既然题目没有要求操作次数最少，那么我们能操作的地方就操作一次，这样最后没有被操作到的就只能是无法操作的地方了。

细节看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool a[55][55],b[55][55];
vector<pair<int,int> > ans;
int main(){
    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][j]&&a[i+1][j]&&a[i][j+1]&&a[i+1][j+1])ans.push_back(make_pair(i,j)),b[i][j]=b[i+1][j]=b[i][j+1]=b[i+1][j+1]=1;//如果a[i][j]、a[i][j+1]、a[i+1][j]和a[i+1][j+1]都为1的话我们才能在(i,j)操作一次，更新b
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)if(b[i][j]^a[i][j])return !printf("-1");//如果a和b有不一样的地方那肯定就是无解了
    printf("%d\n",ans.size());
    for (vector<pair<int,int> >::iterator it=ans.begin();it!=ans.end();it++)printf("%d %d\n",it->first,it->second);//输出
}