1 /*
2 题意：告诉起点终点，踩一次, '.'变成'X'，再踩一次，冰块破碎，问是否能使终点冰破碎
3 DFS：如题解所说，分三种情况：1. 如果两点重合，只要往外走一步再走回来就行了；2. 若两点相邻，
4 那么要不就是踩一脚就破了或者踩一脚走开再走回来踩一脚破了；3. 普通的搜索看是否能到达，
5 若能还是要讨论终点踩几脚的问题:)
6 DFS 耗时大，险些超时，可以用BFS来做
7 */
8 #include <cstdio>
9 #include <algorithm>
10 #include <cstring>
11 #include <string>
12 #include <iostream>
13 using namespace std;
14
15 const int MAXN = 5e2 + 10;
16 const int INF = 0x3f3f3f3f;
17 int n, m;
18 int sx, sy, ex, ey;
19 char maze[MAXN][MAXN];
20 bool vis[MAXN][MAXN];
21 int dx[4] = {1, -1, 0, 0};
22 int dy[4] = {0, 0, -1, 1};
23
24 void DFS(int x, int y)
25 {
26 vis[x][y] = true;
27 if (maze[x][y] == 'X') return ;
28
29 for (int i=0; i<4; ++i)
30 {
31 int tx = x + dx[i];
32 int ty = y + dy[i];
33
34 if (tx <= n && tx >= 1 && ty <= m && ty >= 1 && !vis[tx][ty])
35 {
36 DFS (tx, ty);
37 }
38 }
39
40 return ;
41 }
42
43 int main(void) //Codeforces Round #301 (Div. 2) C. Ice Cave
44 {
45 //freopen ("C.in", "r", stdin);
46
47 while (scanf ("%d%d", &n, &m) == 2)
48 {
49 memset (vis, 0, sizeof (vis));
50 for (int i=1; i<=n; ++i)
51 {
52 scanf ("%s", maze[i]+1);
53 }
54 scanf ("%d%d", &sx, &sy);
55 scanf ("%d%d", &ex, &ey);
56
57 int cnt = 0; bool flag = false;
58 for (int i=0; i<4; ++i)
59 {
60 int tx = ex + dx[i];
61 int ty = ey + dy[i];
62 if (tx == sx && ty == sy) flag = true;
63 if (tx <= n && tx >= 1 && ty <= m && ty >= 1 && maze[tx][ty] == '.') cnt++;
64 }
65
66 if (sx == ex && sy == ey)
67 {
68 if (cnt >= 1) puts ("YES");
69 else puts ("NO");
70 }
71 else if (flag)
72 {
73 if (maze[ex][ey] == 'X') puts ("YES");
74 else
75 {
76 if (cnt >= 1) puts ("YES");
77 else puts ("NO");
78 }
79 }
80 else
81 {
82 maze[sx][sy] = '.';
83 DFS (sx, sy);
84 if (vis[ex][ey])
85 {
86 if (maze[ex][ey] == 'X') puts ("YES");
87 else if (cnt >= 2) puts ("YES");
88 else puts ("NO");
89 }
90 else puts ("NO");
91 }
92 }
93
94 return 0;
95 }
![]()
1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4 #include <queue>
5 #include <string>
6 #include <iostream>
7 using namespace std;
8
9 const int MAXN = 5e2 + 10;
10 const int INF = 0x3f3f3f3f;
11 int n, m;
12 int sx, sy, ex, ey;
13 char maze[MAXN][MAXN];
14 bool vis[MAXN][MAXN];
15 int dx[4] = {1, -1, 0, 0};
16 int dy[4] = {0, 0, -1, 1};
17
18 bool BFS(void)
19 {
20 queue<pair<int, int> > Q;
21 Q.push (make_pair (sx, sy));
22
23 while (!Q.empty ())
24 {
25 int x = Q.front ().first; int y = Q.front ().second; Q.pop ();
26 for (int i=0; i<4; ++i)
27 {
28 int tx = x + dx[i];
29 int ty = y + dy[i];
30
31 if (tx == ex && ty == ey) return true;
32
33 if (tx <= n && tx >= 1 && ty <= m && ty >= 1 && maze[tx][ty] == '.')
34 {
35 maze[tx][ty] = 'X';
36 Q.push (make_pair (tx, ty));
37 }
38 }
39 }
40
41 return false;
42 }
43
44 int main(void) //Codeforces Round #301 (Div. 2) C. Ice Cave
45 {
46 //freopen ("C.in", "r", stdin);
47
48 while (scanf ("%d%d", &n, &m) == 2)
49 {
50 memset (vis, 0, sizeof (vis));
51 for (int i=1; i<=n; ++i)
52 {
53 scanf ("%s", maze[i]+1);
54 }
55 scanf ("%d%d", &sx, &sy);
56 scanf ("%d%d", &ex, &ey);
57
58 int cnt = 0; bool flag = false;
59 for (int i=0; i<4; ++i)
60 {
61 int tx = ex + dx[i];
62 int ty = ey + dy[i];
63 if (tx == sx && ty == sy) flag = true;
64 if (tx <= n && tx >= 1 && ty <= m && ty >= 1 && maze[tx][ty] == '.') cnt++;
65 }
66
67 if (sx == ex && sy == ey)
68 {
69 if (cnt >= 1) puts ("YES");
70 else puts ("NO");
71 }
72 else if (flag)
73 {
74 if (maze[ex][ey] == 'X') puts ("YES");
75 else
76 {
77 if (cnt >= 1) puts ("YES");
78 else puts ("NO");
79 }
80 }
81 else
82 {
83 maze[sx][sy] = '.';
84 //DFS (sx, sy);
85 if (BFS () == true)
86 {
87 if (maze[ex][ey] == 'X') puts ("YES");
88 else if (cnt >= 2) puts ("YES");
89 else puts ("NO");
90 }
91 else puts ("NO");
92 }
93 }
94
95 return 0;
96 }
BFS做法
