小米应用商店_广西互联网企业_日结app推广联盟_网页设计个人主页模板

题目链接

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

思路

直接暴力$bfs$即可。

从起点开始，向四个方向进行扩展，每到达一个节点就修改一下该节点的状态（如果该节点是完整的冰块），如果能走到终点就是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;
}