CSP认证201312-5 I’m stuck![C++题解]：dfs、两次dfs

文章目录

• • • 题目解答
    • 题目链接

题目解答

来源：acwing

分析：

条件1：可以从起点走到该点。用st1[][]数组表示能否从起点到达该点。

条件2：不可以从该点走到终点。

对于条件2的处理：从终点反向遍历能到达的点，就是所有可以走到终点的点。打上标记，剩下的是满足条件2的点。用st2[][]数组表示能否从终点反向到达该点。

求满足条件1和2的点的数量。

下面是4个方向，用两个数组dx[] 和 dy[]表示。

// 方向dx和dy int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

ac代码
下面对这句代码进行解释：if(check(a,b, i ^ 2)) dfs2(a, b);其中check函数用来检查该点是否可以行走，比如可以上下左右走，可以朝下走等。(a,b)是当前点的坐标，后面的i ^2表示方向，啥方向呢？ i表示方向，i ^2表示i的反方向。 这里需要结合上图理解。因为我们的方向是0~3，即i的取值是0 ~ 3。0的反方向是2，1的反方向是3，而i ^2满足什么性质呢？ 恰好1和2异或得到3，2和2异或得0，即恰好实现了反方向！！！

#include<bits/stdc++.h> using namespace std; const int N = 55; int n, m; char g[N][N]; // st1[x][y] = true 表示能从起点到达(x,y) // st2[x][y] = true 表示 能从终点 反向遍历到(x,y) bool st1[N][N], st2[N][N]; // 方向dx和dy int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};// 判断当前点（x,y）是否可走 // k 表示方向，用0~3表示 bool check(int x, int y , int k){char c = g[x][y];// 可上下左右四个方向走if(c == '+' || c == 'S' || c == 'T') return true;// 只能左右走，k为1或者3，即奇数if(c == '-' && k %2 == 1) return true;// 只能上下走，k为0或2，即偶数if(c == '|' && k % 2 == 0) return true;// 只能往下走，k为2if( c == '.' && k == 2) return true;// 其他情况都是不能走return false; } //从起点开始遍历 void dfs1(int x, int y){st1[x][y] = true; //从起点开始能遍历到的点，标记为truefor(int i = 0; i< 4; i++){int a = x + dx[i], b = y + dy[i];if(a < 0 || a >= n || b<0 || b>=m || g[a][b] == '#') continue;if(st1[a][b]) continue;if(check(x, y, i)) dfs1(a, b);} } //从终点开始遍历 void dfs2(int x, int y){st2[x][y] = true;for(int i =0; i< 4; i++){int a = x + dx[i], b= y + dy[i];if(a < 0 || a >= n || b < 0 || b>=m || g[a][b] =='#') continue;if(st2[a][b]) continue;//反向遍历，方向是反的，i 异或2 就表示反方向if(check(a,b, i ^ 2)) dfs2(a, b);} }int main(){cin >> n >> m;for(int i = 0; i< n; i++)for(int j = 0; j<m; j++) cin >> g[i][j];int tx, ty;// 保存终点坐标，目的：是否输出stuckfor(int i = 0; i< n; i++)for(int j = 0; j< m; j++){//如果是起点，开始第一次遍历if(g[i][j] == 'S') dfs1(i,j);else if(g[i][j] == 'T'){tx = i ,ty = j;dfs2(i, j); // 从终点开始反向遍历}}// 如果从起点无法到达终点，则输出stuckif(!st1[tx][ty]) puts("I'm stuck!");else{int res = 0;for(int i = 0; i< n; i++)for(int j = 0; j< m; j++){if(st1[i][j] && !st2[i][j])res ++;}cout << res << endl;}}

题目链接

https://www.acwing.com/problem/content/3199/

总结

以上是生活随笔为你收集整理的CSP认证201312-5 I’m stuck![C++题解]：dfs、两次dfs的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。