当前位置：首页 > article >正文

Codeforces Round 301 (Div. 2) C题 Ice Cave（BFS）

article 2024/9/30 2:15:18

题目链接

https://codeforces.com/problemset/problem/540/C

思路

直接暴力 $b f s$ 即可。

从起点开始，向四个方向进行扩展，每到达一个节点就修改一下该节点的状态（如果该节点是完整的冰块），如果能走到终点就是YES，否则就是NO。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e2 + 5;
int n, m;
int r[2], c[2];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
char s[N][N];
void bfs()
{
	queue<pair<int, int>>q;
	q.push({r[0], c[0]});
	while (q.size())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int tx = x + dx[i];
			int ty = y + dy[i];
			if (tx == r[1] && ty == c[1] && s[tx][ty] == 'X')
			{
				cout << "YES" << endl;
				return;
			}
			if (s[tx][ty] == '.')
			{
				s[tx][ty] = 'X';
				q.push({tx, ty});
			}
		}
	}
	cout << "NO" << endl;
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> s[i][j];
		}
	}
	for (int i = 0; i < 2; i++)
	{
		cin >> r[i] >> c[i];
	}
	bfs();
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	// cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}