题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<sstream>

using namespace std;
const int N = 15;
char g[N][N];
int n, m;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int bfs()
{
    queue<pair<int, int>> q;
    for (int i = 0; i < n;  i ++)
        for (int j = 0; j < m; j ++)
            if (g[i][j] == '2')
            {
                q.push({i, j});
            }
    int k = -1;
    while(q.size())
    {
        int size = q.size();
        k ++;
        while(size --)
        {
            auto t = q.front(); q.pop();
            int x = t.first, y = t.second;
            for (int i = 0; i < 4; i ++)
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b <= m && g[a][b] == '1')
                {
                    q.push({a, b});
                    g[a][b] = '2';
                }
            }
        }
    }
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (g[i][j] == '1') return -1;
    return k;
}
int main()
{
    string line;
    while(getline(cin, line))
    {
        int k = 0;
        stringstream ssin(line);
        while(ssin >> g[n][k]) k ++;
        m = k;
        n ++;
    }
    cout << bfs() << endl;
    return 0;
}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla