CF920A Water The Garden (BFS水题)

原题链接

题目

思路

直接 BFS 即可，把所有状态放进去，这里初始化了所有状态为 1 ，也就是说已经把自己本身给灌溉了，然后 BFS 扩展每个可以扩展的点放进去，能扩展就扩展，然后标记一下，左后取最大值即可，因为可以扩展时一定时间会变长，不可以扩展时，时间也不会变长了，所以直接取最大值，然后输出答案。

注意向左扩展时不能是负数。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2500;
bool st[N];
int n, m;
struct name{
    int l, r, cnt;
};
int main()
{
    int t;cin >> t;while (t -- ){
    cin >> n >> m;queue<name> q;memset (st, 0, sizeof st);for (int i= 1; i <= m; i ++ ){
    int x;cin >> x;q.push({
    x, x, 1});st[x] = 1;}int ans = 0;while (!q.empty()){
    auto t = q.front();q.pop();ans = max(ans, t.cnt);int l = t.l, r = t.r, cnt = t.cnt;
// cout << l << " " << r << endl;if ((!st[l - 1] && l - 1 >= 1 )|| (!st[r + 1] && r + 1 <= n)){
    st[l - 1] = 1;st[r + 1] = 1;q.push({
    max(l - 1, 0), r + 1, cnt + 1});}}cout << ans << endl;}return 0;
}

总结

简单。