题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<limits.h>

using namespace std;
typedef pair<int, int> PII;
const int N = 260;

int n, m;
char g[N][N];
int dist[N][N];

void bfs(int k)
{
    queue<PII> q;
    memset(dist, -1, sizeof dist);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (g[i][j] == '1')
            {
                q.push({i, j});
                dist[i][j] = 0;
            }

    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    while(q.size())
    {
        auto t = q.front();q.pop();
        int x = t.first, y = t.second;
        int distance = dist[x][y];
        if (distance == k) break;
        for (int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 1 && a <= n && b >= 1 && b <= m && dist[a][b] == -1)
            {
                q.push({a, b});
                dist[a][b] = distance + 1;
            }
        }
    }
}
bool check(int k)
{
    bfs(k);
    int min_sum = INT_MAX, max_sum = INT_MIN, min_sub = INT_MAX, max_sub = INT_MIN;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (dist[i][j] == -1)
            {
                min_sum = min(min_sum, i + j);
                max_sum = max(max_sum, i + j);
                min_sub = min(min_sub, i - j);
                max_sub = max(max_sub, i - j);
            }
    if (min_sum == INT_MAX) return true;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (g[i][j] == '0')//这里用这个判断条件；
            {
                int sum = max(abs(i + j - min_sum), abs(i + j - max_sum));
                int sub = max(abs(i - j - min_sub), abs(i - j - max_sub));
                if (max(sum, sub) <= k) return true;
            }
    return false;
}

int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; C ++)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i ++) cin >> g[i] + 1;

        int l = 0, r = n + m;
        while(l < r)
        {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("Case #%d: %d\n", C, l);
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla