C++课后习题训练记录Day151-北京尧图网络

1.练习项目问题描述给定一个 n×n 的矩阵其中 A 代表起点C 代表终点。起点永远在左上角终点永远在右下角。对于矩阵中其余的点O 代表可以通过X 代表路障。我们可以向上下左右移动但是不能斜走不能走进为路障的点也不能超出矩阵范围。我们可以在任意为 O 的点放置路障求至少放置几个路障能使得从起点出发无法走到终点输入格式第一行为一个正整数 T为样例组数。对于每组样例第一行为一个正整数 n含义见问题描述。接下来是一个 n×n 的矩阵仅由大写字母 A,C,O,X 构成。输出格式输出 T 行每行一个整数为放置路障的个数。2.选择课程在蓝桥云课中选择题库选择题号3567并开始练习。3.开始练习1源码#includebits/stdc.h#define pi acos(-1)using namespace std;#define ll long longstring s[5005];bool vis[5005][5005];int n;bool check(int i, int j) {if (i 0 || j 0 || i n || j n) return 0;if (vis[i][j] 1) return 0;return 1;}bool check2(int i, int j) {if (i 0 || j 0 || i n || j n) return 0;return 1;}bool dfs1(int i, int j) {//cout i j endl;stackpairint, int p;p.push({ i,j });while (!p.empty()) {pairint, int t p.top();p.pop();if (s[t.first][t.second] C) return 1;if (check(t.first 1, t.second) s[t.first 1][t.second] ! X) {vis[t.first 1][t.second] 1;p.push({ t.first 1,t.second });}if (check(t.first, t.second 1) s[t.first][t.second 1] ! X) {vis[t.first][t.second 1] 1;p.push({ t.first , t.second 1 });}if (check(t.first - 1, t.second) s[t.first - 1][t.second] ! X) {vis[t.first - 1][t.second] 1;p.push({ t.first - 1, t.second });}if (check(t.first, t.second - 1) s[t.first][t.second - 1] ! X) {vis[t.first][t.second - 1] 1;p.push({ t.first , t.second - 1 });}}return 0;}pairint, int d[] { {1,0} ,{0,1},{-1,0},{0,-1},{-1,-1},{1,1} ,{1,-1},{-1,1} };void dfs2(int i, int j, int t) {s[i][j] 0 t;stackpairint, int p;p.push({ i,j });while (!p.empty()) {pairint, int q p.top();s[q.first][q.second] 0 t;p.pop();for (int i 0; i 8; i) {if (check(q.first d[i].first, q.secondd[i].second) s[q.first d[i].first][q.second d[i].second] X) {vis[q.first d[i].first][q.second d[i].second] 1;p.push({ q.first d[i].first,q.second d[i].second });}}}}bool dfs3(int i, int j) {setchar st;if (check2(i 1, j)) st.insert(s[i 1][j]);else st.insert(3);if (check2(i, j 1)) st.insert(s[i][j 1]);else st.insert(4);if (check2(i - 1, j)) st.insert(s[i - 1][j]);else st.insert(1);if (check2(i, j - 1)) st.insert(s[i][j - 1]);else st.insert(2);if (check2(i 1, j - 1)) st.insert(s[i 1][j - 1]);if (check2(i - 1, j 1)) st.insert(s[i - 1][j 1]);if (check2(i - 1, j - 1)) st.insert(s[i - 1][j - 1]);if (check2(i 1, j 1)) st.insert(s[i 1][j 1]);if (st.count(1) (st.count(2) || st.count(3))) return 1;if (st.count(2) st.count(4)) return 1;if (st.count(3) st.count(4)) return 1;return 0;}int main() {int T;cin T;while (T--) {cin n;for (int i 0; i n; i) {cin s[i];}memset(vis, 0, sizeof vis);if (dfs1(0, 0) 0) {cout 0 endl;continue;}if (s[0][1] X || s[1][0] X || s[n - 2][n - 1] X || s[n - 1][n - 2] X) {cout 1 endl;continue;}memset(vis, 0, sizeof vis);for (int i 1; i n; i) {if (s[0][i] X) dfs2(0, i, 1);}for (int i 1; i n; i) {if (s[i][0] X) dfs2(i, 0, 2);}for (int i 1; i n; i) {if (s[n - 1][i] X) dfs2(n - 1, i, 3);}for (int i 1; i n - 1; i) {if (s[i][n - 1] X) dfs2(i, n - 1, 4);}bool re 0;for (int i 0; i n; i) {for (int j 0; j n; j) {if (s[i][j] O) {re dfs3(i, j);if (re 1) break;}}if (re 1) break;}if (re) {cout 1 endl;}else cout 2 endl;}return 0;}2检验结果对此代码进行检验检验后无报错提交此代码判题结果为正确100分。3练习心得解题思路本题可以转化为求 A 到 C 的连通性问题所以很容易想到 tarjan 算法但是本题精心构造的数据会使得 tarjan 算法无法通过。观察矩阵我们可以得出以下结论结论如果起点的下方和右方均为路障或终点的上方和左方均为路障那么无需放置A 和 C 一定不连通这时候无需放置路障。推论一我们可以在起点下方和右方或终点的上方和左方放置路障即可使得 AC 不连通。可以得出最坏情况为放置两个路障。推论二如果起点的下方或右方有路障或终点的上方或左方有路障那么我们只需要放置一个路障就能达成上面的情况使得 A 和 C 不连通。如下图我们将矩阵边缘视为墙并进行编号。可以发现按照 12132434 连接两面墙可以使得 A 和 C 不连通。所以我们需要判断是否能够添加一个路障使得路障之间形成上述的连接。所以我们可以对矩阵进行三次 dfs第一次判断 AC 是否连通如果不连通那么就不需要放置任何路障。第二次如下图按照所连接的墙壁编号为连接到不同墙壁的路障染色。第三次搜索所有已经染色的墙如果和他距离为 22 有其他已经染色的墙并且可以构成 12132434 四种组合的任意之一则需要放置一个路障否则根据上述的推论一输出 22。注意事项本题为了卡掉 tarjan 构造的极限数据可能使得递归 dfs 超时或爆栈所以应使用非递归。注意每段代码末尾的分号是否存在如不存在则需即使补充输入法是否切换为英语模式语法是否错误。

C++课后习题训练记录Day151

相关推荐

FreeRTOS 学习笔记：裸机系统与多任务系统

d2s-editor：革新暗黑破坏神2存档编辑体验的可视化工具

电脑的安装与卸载

更多资讯

VC2015编译libssh-0.10.3静态库：Windows下SFTP集成确定性方案

土木工程师转型网络安全的路径与实战分析

Java数据结构选型指南：从原理到性能优化实战

动态规划与贪心算法在多边形周长问题中的应用

VS Code SFTP插件实现跨平台文件同步实战

Spring Boot应用Docker容器化与Nginx部署实践

今日更新

AI辅助技术栈评估：提升研发决策效率60%

从生成Token到直接决策：Jev如何重塑AI Agent工程实践

32G统一内存跑大模型：内存账、TPS实测与端云分流

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？