这题代码虽然长,但写出来比较对称还是挺好看的
根据y总的结论,任意一个数为1时,我们都可以通过三次操作在不影响其他点的情况下,将其转换为0,即如图所示的方法:
而操作数的限制为 $3nm$, 所以就算把每一个点都进行三次操作都是满足这个限制的
显然第一问的答案输出给定矩阵中1的个数乘以3即可。
这是其中一种方案,只适用于该点能够向下,右,右下扩展的情况,但其实有四种情况,分别对应了如图的外围上的点:
相同的颜色可以对应同一种变换方式,只需要分四种情况讨论即可:
1.红色对应 $i < n\space且\space j = 1$:选择以该点为左上角的矩阵
2.绿色对应 $i = 1\space且\space j > 1$:选择以该点为右上角的矩阵
3.黄色对应 $i = n\space且\space j < m$:选择以该点为左下角的矩阵
4.蓝色对应 $i > 1\space且\space j = m$:选择以该点为右下角的矩阵
很明显可以看出来除了外围的那一圈,中间的点可以采用任意一种方式变换
这里的注释的各个方位均以当前选择的矩阵的左上角为参考系
Code:
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
char s[N][N];
void print1(int i, int j) { //左下,左上,右上
printf("%d %d %d %d %d %d\n", i, j, i, j + 1, i + 1, j);
}
void print2(int i, int j) { //左上,左下,右下
printf("%d %d %d %d %d %d\n", i, j, i + 1, j, i + 1, j + 1);
}
void print3(int i, int j) { //左上,右上, 右下
printf("%d %d %d %d %d %d\n", i, j, i, j + 1, i + 1, j + 1);
}
void print4(int i, int j) { //左下,右下,右上
printf("%d %d %d %d %d %d\n", i + 1, j, i, j + 1, i + 1, j + 1);
}
int main() {
int T;
cin >> T;
while (T -- ) {
int ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) scanf("%s", s[i] + 1);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (s[i][j] == '1') ans += 3;
cout << ans << endl;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (s[i][j] == '1') {//这里每次传进去的i,j对应要选择的矩阵的左上角,要做一些转换
if (i == 1 && j < m) {
print1(i, j);
print2(i, j);
print3(i, j);
continue;
} else if (j == 1 && i > 1) {
print1(i - 1, j);
print2(i - 1, j);
print4(i - 1, j);
continue;
} else if (i == n && j > 1) {
print2(i - 1, j - 1);
print3(i - 1, j - 1);
print4(i - 1, j - 1);
continue;
} else if (j == m && i < n) {
print1(i, j - 1);
print3(i, j - 1);
print4(i, j - 1);
continue;
} else {
print1(i, j);
print2(i, j);
print3(i, j);
}
}
}
return 0;
}
哎,我还在傻傻地dfs
tql
%%%%
s[i]+1为何能表示二维数组
哦噢,原来是%s是我理解错了
嗯,它读的是首地址
scanf(“%s”, s[i] + 1);
请问为什么要加1呢
下标从1开始读入,习惯从1开始
这种有-1的操作一般从1开始可以避免弄些边界问题出来