2022.11.28.CodeForces

CodeForces"/>

2022.11.28.CodeForces

原题链接：传送门 

 题意：

在一个 n×m 的网格中，有些格子是完整的冰块，有些是破碎的冰块。如果你走到完整的冰块上，下一秒它会变成碎冰；如果你在碎冰上，你会掉下去。你不能在原地停留。

现在你在 (r1​,c1​) 上，保证该位置是一块碎冰。你要从(r2​,c2​) 掉下去，问是否可行。

思路：

嗯这道题很容易就想到bfs但其实dfs更简单点，其实题意再转化是要至少经过一次终点(因为如果终点是'.',那么需要经过终点一次使'.'变'X'再到终点才能从该点顺利掉下去，这不大不小的数据范围也不必担心爆栈问题，那么直接去递归就好了。

所以dfs做法:

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
char g[N][N];
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n, m, a, b, c, d;
int dfs(int x, int y) {if (g[x][y] != '.') return (x == c and y == d);g[x][y] = 'X';for (int i = 0; i < 4; i++)if (dfs(x + dx[i], y + dy[i]))return 1;return 0;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> (g[i] + 1);cin >> a >> b >> c >> d;g[a][b] = '.';puts(dfs(a, b) ? "YES" : "NO");return 0;
}

bfs做法

这个做法就比较好想，要注意的是开一个数组来记录每个冰块的状态，以此来保证走至少走两遍终点；

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 505;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
char s[N][N];
int cnt[N][N];
int n, m, sx, sy, ex, ey;
bool bfs(){queue<PII> q;q.push({sx, sy});cnt[sx][sy] = 0;while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int a = t.x + dx[i], b = t.y + dy[i];if (a <= 0 || a > n || b <= 0 || b > m) continue;if (!cnt[a][b]){if (a == ex && b == ey) return 1;}else q.push({a, b}), cnt[a][b]--;}}return 0;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 0; i < n; i++) cin >> s[i];for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (s[i][j] == '.') cnt[i + 1][j + 1] = 1;else cnt[i + 1][j + 1] = 0;cin >> sx >> sy >> ex >> ey;puts(bfs() ? "YES" : "NO");return 0;
}