当前位置: 首页 > news >正文

洛谷B4040 [GESP202409 四级] 黑白方块 题解

原题传送门

前言

天啊!上一周刚刚考完 \(CSP-J\) ,这一周就得去考 \(GESP\) 4级 (是的,你没有听错,我3级过了!)
所以,做了一道简单的题之后,我又来写题解了!
(仍然是WA++)

题目解析

哇,这题可真长啊!什么 (可恶的) 小杨有一个 \(n\)\(m\) 列的网格图,其中每个格子要么是白色,要么是黑色……之类的。简单总结一下:

  1. 每一个测试点里有一共 \(t\) 组数据,老规矩:用 memset() 做初始化。
  2. 每组测试数据包含:一个 \(n\)\(m\) 以及一个大小为 \(n \times m\) 的二维矩阵。
  3. 让你找是否有一个如下的连续的子矩阵 (你应该知道连续子矩阵是啥意思吧?)
0000
0110
0110
0000
  1. 如果有,输出 Yes 否则,输出 No 即可。

思路解析

这道题看似需要复杂的算法,实际上…… 看看这感人的数据规模:

对全部的测试数据,保证 \(1 \leq t\leq 10\)\(1 \leq n,m \leq 100\)

也就是说,其实只需要模拟即可通过!
即,遍历所有的可能的子矩阵起点:

for (int i = 1; i <= n - 3; i++) {for (int j = 1; j <= m - 3; j++) {if (check(i, j))flag = true;}
}

接着在 check() 函数里去判断,以 (i,j) 为起点的 \(4 \times 4\) 矩阵是否合规。

bool check(int x, int y) {for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {if (c[i + x][j + y] != g[i][j])return false;}}return true;
}

唉,同样是2024年9月的题,3级第一题(详见它)就如此难,暴力也过不了。
而4级的题目,就非常人性化!

AC Code

点击查看完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 110;
int n, m;
int a[N][M];
int t;
int mp[4][4] = {{0, 0, 0, 0},{0, 1, 1, 0},{0, 1, 1, 0},{0, 0, 0, 0}
};bool check(int x, int y) {for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {if (a[x + i][y + j] != mp[i][j]) {return false;}}}return true;
}int main() {cin >> t;while (t--) {memset(a, 0, sizeof(a));cin >> n >> m;for (int i = 1; i <= n; i++) {string s;cin >> s;for (int j = 1; j <= m; j++) {a[i][j] = s[j - 1] - '0';}}bool flag = false;for (int i = 1; i <= n - 3; i++) {for (int j = 1; j <= m - 3; j++) {if (check(i, j)) {flag = true;break;}}if (flag) break;}if (flag) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

完结撒花!(补药再抄代码了!)

http://www.hskmm.com/?act=detail&tid=15088

相关文章:

  • SerpApi:一站式搜索引擎数据抓取API完全指南
  • 补whk时的鲜花(持续更新)
  • css 使用记录 随笔
  • newDay02
  • 【OI 档案-2025】CSP 赛前集训记(初赛后+复赛)
  • Git 从零到一:以 Gitee 为例的实战与可视化指南
  • 代码随想录算法训练营第七天 |第454题.四数相加II、383. 赎金信、第15题. 三数之和
  • day06
  • 前沿速览:TrafficVLM、DeepSeek-Terminus、Qwen3-Omni、蚂蚁百灵、Wan2.2-Animate、Qianfan-VL
  • 代码随想录算法训练营第七天 | leetcode 454 383 15 18
  • 概率期望
  • Day2
  • 2025.9.23总结 - A
  • 8
  • 从3亿到48亿:NuGet周下载量跃迁背后的.NET生态演进与未来挑战(2019-2025)
  • 实用指南:PHP 使用说明
  • 9月23号
  • CF520E Pluses everywhere 题目分析
  • java里面的IO流分为哪几种,他们的区别是什么呢
  • ReLU函数及它的导数
  • 基础数论
  • 第一次个人编程作业-论文查重
  • 使用Claude代码子代理生成项目特定提交消息的技术实践
  • 走迷宫(BFS)
  • MyBatis分页的原理和分页插件的原理是什么
  • 达成度报告
  • 旋转图像-leetcode
  • 【ChipIntelli 系列】ASR部分——合成语言模型和多网络(多语种)切换
  • 内网环境怎么安装软件(用 yum / apt 下载离线包并搬入内网)