题目描述
给定一个 n×m\mathrm{n \times m}n×m 的迷宫，迷宫由 "#" 与"." 两种字符组成。其中 "#" 代表障碍物，"." 表示空地。迷宫中还有一个起点 "S" 和一个终点 "E" ，它们都可以视为空地。由于近期迷宫发生了塌方，导致起点和终点之间可能并不连通。幸运的是，你拥有一种超能力——在迷宫中移动时（移动方向为上、下、左、右四个方向之一），可以在当前位置朝任一方向（上、下、左、右四个方向之一）释放激光。激光能够清除该方向上所有的障碍物，并且这种超能力至多只能使用一次。
现在，你需要判断是否能利用这种超能力成功从起点到达终点。
输入描述:
第一行给定两个整数n,m(2≤n,m≤1000)，分别表示迷宫的行数和列数。 下面n行，每行m个字符，描述迷宫的具体布局。字符只包含"#"、"."、"S"和"E"，并且起点与终点有且仅有一个。
输出描述:
能够到达终点输出YES,否则输出NO。
示例1输入
4 5 .#### S#### .#### .E###
输出
YES
示例2
输入
4 5 ..### S#### ##### ##.E#
输出
YES
说明
显然可以从起点出发，到达(1,2)\mathrm{(1,2)}(1,2)处并向下方使用超能力，此时可以从起点到达终点。
示例3
输入
4 5 ..### S#### ##### ###E#
输出
NO
问题的关键在于可以清除某个方向的障碍物，我一开始想用DFS+回溯去暴力破解，但回溯需要修正的变量过于繁琐且时间复杂度爆炸，只能另取他法。
通过观察可以发现，对起点和终点都进行遍历，设与起点连通的点集为x，与终点连通的点集为y，任取y中一点y1，若在y1的相邻行或列以及本行中存在x中的某点，那就可以通过清除障碍进行连通。
所以释放激光后起点与终点连通 等价于 起点所在连通块与终点所在连通块存在相邻或相同的行/列，因此可以考虑分别从起点与终点进行两遍DFS，从终点出发的DFS标记出其能够直接到达的行列坐标；从起点出发的
DFS枚举每个位置以及释放激光的方向，判断是否可能连通。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m;
4 int s_x, s_y, e_x, e_y;
5 bool result = false;
6 char graph[1005][1005];
7 int visited[1005][1005];
8 bool row[1005],column[1005];
9
10 void dfs(int x, int y, int orientation){
11 visited[x][y] = orientation;
12 if (orientation == 1){
13 row[x] = 1;
14 column[y] = 1;
15 }
16 if (x == e_x && y == e_y && orientation == 1){
17 result = true;
18 return;
19 }
20 if (x == s_x && y == s_y && orientation == 2){
21 result = true;
22 return;
23 }
24 if (orientation == 2){
25 for (int i = x - 1; i <= x + 1; ++i){
26 if (i > 0 && i <= n && row[i]){
27 result = true;
28 return;
29 }
30
31 }
32 for(int j = y - 1; j <= y + 1; ++j){
33 if (j > 0 && j <= m && column[j]){
34 result = true;
35 return;
36 }
37 }
38 }
39 if (visited[x - 1][y] == 0 && graph[x - 1][y] != '#'){
40 dfs(x - 1, y, orientation);
41 }
42 if (visited[x + 1][y] == 0 && graph[x + 1][y] != '#'){
43 dfs(x + 1, y, orientation);
44 }
45 if (visited[x][y - 1] == 0 && graph[x][y - 1] != '#'){
46 dfs(x, y - 1, orientation);
47 }
48 if (visited[x][y + 1] == 0 && graph[x][y + 1] != '#'){
49 dfs(x, y + 1, orientation);
50 }
51
52 }
53 int main(){
54 memset(graph, '#', sizeof(graph));
55 memset(visited, 0, sizeof(visited));
56 memset(row, false, sizeof(row));
57 memset(column, false, sizeof(row));
58 cin>>n>>m;
59 for (int i = 1; i <= n; ++i){
60 for (int j = 1; j <= m; ++j){
61 cin>>graph[i][j];
62 if (graph[i][j] == 'S'){
63 s_x = i; s_y = j;
64 }
65 if (graph[i][j] == 'E'){
66 e_x = i; e_y = j;
67 }
68 }
69 }
70 dfs(s_x, s_y, 1);
71 if (result){
72 cout<<"YES"<<endl;
73 return 0;
74 }
75 dfs(e_x, e_y, 2);
76 if (result)
77 cout<<"YES"<<endl;
78 else
79 cout<<"NO"<<endl;
80 }
标签：连通,终点,int,迷宫,DFS,99,牛客,&&,起点 From： https://www.cnblogs.com/coderhrz/p/18378053