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

本文主要是介绍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;}}