[关闭]
@oujunsong 2023-05-04T17:29:26.000000Z 字数 770 阅读 149
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 505;
  4. int n, m, ans, tt;
  5. char a[N][N];
  6. int dir[4][6] = {{0, 0, 1, 0, 0, 1}, {0, 0, -1, 0, 0, -1},
  7. {0, 0, -1, 0, 0, 1}, {0, 0, 1, 0, 0, -1}};
  8. int main() {
  9. freopen("cover.in", "r", stdin);
  10. freopen("cover.out", "w", stdout);
  11. cin >> n >> m;
  12. for (int i = 1; i <= n; i++) {
  13. for (int j = 1; j <= m; j++) {
  14. cin >> a[i][j];
  15. if (a[i][j] == '1') tt++;
  16. }
  17. }
  18. int minn = 1e9;
  19. for (int i = 1; i <= n; i++) {
  20. for (int j = 1; j <= m; j++) {
  21. for (int k = 0; k < 4; k++) {
  22. int dx = i + dir[k][0], dy = j + dir[k][1];
  23. int dx1 = i + dir[k][2], dy1 = j + dir[k][3];
  24. int dx2 = i + dir[k][4], dy2 = j + dir[k][5];
  25. if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && dx1 >= 1 && dx1 <= n && dy1 >= 1 && dy1 <= m && dx2 >= 1 && dx2 <= n && dy2 >= 1 && dy2 <= m) {
  26. int res = 0;
  27. if (a[dx][dy] == '1') res++;
  28. if (a[dx1][dy1] == '1') res++;
  29. if (a[dx2][dy2] == '1') res++;
  30. if (res < minn && res) {
  31. minn = res;
  32. }
  33. }
  34. }
  35. }
  36. }
  37. // minn 则为第一次 L 形最少覆盖 1 的数量,tt为矩形中 1 的数量,以下结论则显然推出
  38. cout << tt - minn + 1 << endl;
  39. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注