关键词
图通路，DFS/BFS
题目
思路
几点想说明的：
- 为什么要两个DFS；dfs1表示的是求从S出发能到达的所有的点；dfs2是考虑从T出发回溯，能到达的所有点，回溯去走，相当于此时T才是起点
- check函数：这个是用来判断当前点能不能走；因此dfs1和dfs2中的check的变量是不一样的；
- 本人狠狠踩坑的点：很久没撸代码了，直接int g[N][N];一直segmentation fault；后来重新码了一遍，才后知后觉！
代码
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
const int N=55;
char g[N][N];
bool st1[N][N],st2[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool check(int x,int y,int k){if(g[x][y] == 'T' || g[x][y] == '+' || g[x][y] == 'S') return true;// T, +, S 能走到各个方向if(g[x][y] == '.' && k == 2) return true;// . 只能向下走 if(g[x][y] == '-' && (k == 1 || k == 3)) return true;// - 向左向右走if(g[x][y] == '|' && (k == 0 || k == 2)) return true;// | 向上向下走return false;
}void dfs1(int x, int y)//深度优先遍历，求出 S 能到的所有点
{st1[x][y] = true;//能走到当前点，状态置为 truefor(int i = 0; i < 4; i++)//向4个方向走{int a = x + dx[i], b = y + dy[i];if(check(x, y, i) && !st1[a][b] && g[a][b] != '#')//如果当前位置能走到下一位置，并且下一位置没被走过，并且不是 #，走到下一位置dfs1(a, b);}
}void dfs2(int x,int y){ //求出能从T出发到达的所有点st2[x][y] = true;//能走到当前点，状态置为 truefor(int i = 0; i < 4; i++)//向4个方向走{int a = x + dx[i], b = y + dy[i];int k = i ^ 2;if(check(a, b, k) && !st2[a][b] ) //能走回前面的点 此处的check是a,b;因为我们逆向回溯，所以当前点是(a,b)dfs2(a,b);}
}int main(){int n,m;cin>>n>>m;int s_x,s_y,e_x,e_y;memset(g,'#',sizeof(g));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];if(g[i][j]=='S')s_x=i,s_y=j;if(g[i][j]=='T')e_x=i,e_y=j;}}dfs1(s_x,s_y);if(!st1[e_x][e_y]){ //说明没有走到终点cout<<"I'm stuck!"<<endl;return 0;}int res=0;dfs2(e_x,e_y);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(st1[i][j]&&!st2[i][j])res++;}}cout<<res<<endl;return 0;
}
