Codeforces1207-B Square Filling

题目大意:给出两个$n \cdot m$的矩阵$A$和$B$,一开始矩阵$B$全为0,每次可以选定一个坐标$(x,y)(1 \le x < n、1 \le y < m)$,将$(x,y)、(x,y + 1)、(x + 1,y)、(x + 1,y + 1)$都变成1,求将矩阵$B$变为$A$的最小步数,并输出所有的操作的坐标。

这个思维题又把我卡死了,C题都写得出来但是我写不出这个B,结束前3分钟才给A掉然后没时间写别的了。。
要操作的次数最少,也就是说每次操作要保证改变的0的数量最多
把一个0的位置变成1,假设这个坐标是$(x,y)$,那么可以通过修改$(x - 1,y - 1)、(x - 1,y)、(x,y - 1)、(x,y)$这四个位置来达到
那么每次直接扫描一下$B$中是0但$A$中是1的位置,如果操作的区域中在$A$中没有0,就可以求出一个能使得这次操作最大化的操作位置来进行操作
显然时间复杂度是$O(nm)$的,然后我这里还带了一些常数,但是影响不大

这一场从$\Delta$-80+在最后3分钟拉回来。。最后涨了一分。。。(我还真是个弟弟。。
思维题必杀我

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
int n,m;
int a[60][60],b[60][60],cnt = 0;

vector<pair<int,int> > ans;

inline bool check(int x,int y) {
if(a[x][y] == 0 || a[x][y + 1] == 0 || a[x + 1][y] == 0 || a[x + 1][y + 1] == 0) return false;
return true;
}

inline void modify(int x,int y) {
b[x][y] = b[x][y + 1] = b[x + 1][y] = b[x + 1][y + 1] = 1;
}

bool checkans() {
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(b[i][j] != a[i][j]) return false;
}
}
return true;
}

int get_fix(int x,int y) {
if(x < 1 || x >= n || y < 1 || y >= m) return 0;
else {
int cnt = 0;
for(int i = 0;i < 2;i++) {
for(int j = 0;j < 2;j++) {
if(b[x + i][y + j] == 0) cnt++;
}
}
return cnt;
}
}
int main() {
ios::sync_with_stdio(0);
mst(b,0);
cin>>n>>m;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
cin>>a[i][j];
}
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(b[i][j] == 0 && a[i][j] != 0) {
int fixed = 0;
int posx = 0,posy = 0;
for(int k = -1;k <= 0;k++) {
for(int l = -1;l <= 0;l++) {
if(check(i + k,j + l)) {
int tmp = get_fix(i + k,j + l);
if(fixed < tmp) {
fixed = tmp;
posx = i + k;posy = j + l;
}
}
}
}
if(fixed != 0) {
cnt++;
modify(posx,posy);
ans.push_back(make_pair(posx,posy));
}
}
}
}
if(checkans() == false) {
cout<<-1<<endl;
}
else {
cout<<cnt<<"\n";
for(auto x : ans) {
cout<<x.first<<" "<<x.second<<"\n";
}
}
return 0;
}