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 超时或爆栈所以应使用非递归。注意每段代码末尾的分号是否存在如不存在则需即使补充输入法是否切换 为英语模式语法是否错误。