CCF I’m stuck（满分代码 + 解题思路 + 技巧总结） 201312-5

技巧总结

• 数组中上下左右的移动可以使用偏移量数组，方便操作
• 当要遍历数组中的点能否到达点T时，可以通过从点T反向遍历，先反向判断后再移动，遍历到的所有点即正向可达

解题思路

题目中需要找满足 （从起点可以到达该点 && 从该点不能到达终点）这两个条件的点的个数
所以可以开设两个数组记录是否分别满足上述两个条件
st1数组记录从起点可以遍历到的所有点
st2数组记录从终点可以反向遍历到的所有点
反向遍历就是假如你要从(x, y)走到(a, b),你先判断从(a, b)能否走到（x, y),若能，则从（x, y)走到（a,b)
然后同时遍历两个数组，计数满足上述条件点的个数
如果st1中显示从起点无法到达终点则输出“I’m stuck！"

代码实现

#include <iostream>
#include <unordered_map>
#include <cstring>using namespace std;const int N = 60;
typedef pair <int, int> PII;char g[N][N];int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};//st1记录s能够到达的点，st2记录t能到达的点
bool st1[N][N];
bool st2[N][N];void dfs1(int a, int b) //从S正向遍历
{//先预定义每一种符号有哪些移动方向int l = 0, r = 0;if (g[a][b] == '+' || g[a][b] == 'T' || g[a][b] == 'S') l = 0, r = 4;if (g[a][b] == '-') l = 2, r = 4;if (g[a][b] == '|') l = 0, r = 2;if (g[a][b] == '.') l = 1, r = 2; st1[a][b] = true;for (int i = l; i < r; i ++){int x = a + dx[i], y = b + dy[i];if (x < 1 || x > n || y < 1 || y > m || st1[x][y] || g[x][y] == '#') continue;dfs1(x, y);}return ;
}void dfs2(int a, int b) //从T反向遍历
{st2[a][b] = true;for (int i = 0; i < 4; i ++){int x = a + dx[i], y = b + dy[i];if (x < 1 || x > n || y < 1 || y > m || st2[x][y] || g[x][y] == '#') continue;if (g[x][y] == '.' && i != 0) continue; //.只能位于该点上方才合理,才能从.到达该点if (g[x][y] == '-' && i != 2 && i != 3) continue;//.只能位于该点的左右才合理,才能从-到达该点if (g[x][y] == '|' && i != 0 && i != 1) continue;//.只能位于该点的上下才合理,才能从|到达该点dfs2(x, y);}return ;
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++){scanf("%s", g[i] + 1);}PII bn, ed;for (int i = 1; i <= n; i ++){for (int j = 1; j <= m; j ++){if (g[i][j] == 'S') bn = {i, j}; if (g[i][j] == 'T') ed = {i, j};}}memset(st1, false, sizeof(st1));memset(st2, false, sizeof(st2));dfs1(bn.first, bn.second);dfs2(ed.first, ed.second);int res = 0;if (st1[ed.first][ed.second]) //S可以到达T{for (int i = 1; i <= n; i ++){for (int j = 1; j <= m; j ++){if (st1[i][j] && !st2[i][j]) res ++; // S可以到达，T不能到达的点即为答案}}cout << res;}else cout << "I'm stuck!";return 0;
}