11003: 【原1003】二哥养细菌

题目描述

author: xjia 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1003

题目描述

二哥不仅种苹果和花生，还养了很多细菌。二哥的细菌培养皿成方格形，边长为L。长期培养后，二哥发现了细菌繁殖的规律：最初每个格子里的细菌及其后代都会独立繁殖，每次繁殖都会在其上下左右四个相邻的格子里产生新的细菌，而已经存在的细菌在培养皿充满细菌之前都不会死亡。另外，有一些格子里可能还有抗生素，细菌在有抗生素的格子里无法繁殖。

二哥于是发明了一个游戏：取一个新的培养皿，在某些格子里放入细菌或抗生素，然后观察细菌不断繁殖直至充满整个培养皿的所有没有抗生素的格子。不过二哥已经对这个游戏厌烦了，他现在只想知道经过多少轮繁殖后，细菌会充满整个培养皿（不算有抗生素的格子）。

输入格式

第1行有1个整数，边长L。

第2行至第L+1行，每行有L个整数，取值为0、1或2。0表示格子里最初没有细菌，1表示格子里最初有细菌，2表示格子里最初有抗生素。

输出格式

输出一个整数m，表示经过m轮繁殖后，细菌会充满整个培养皿（不算有抗生素的格子）。

说明

【样例解释】第一轮繁殖：

2 1 0

1 1 1

0 1 0

第二轮繁殖：

2 1 1

1 1 1

【数据范围】

对于全部数据：\(1 \leq L \leq 100 \) ，保证最终能够充满培养皿（不算有抗生素的格子）。

Sample Input

Sample Output

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/16.
//
// 广度优先搜索

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

using namespace std;

int N = 100 + 5;

class Point {
public:
    int X;
    int Y;
};

Point ds[] = {{-1, 0},
              {1,  0},
              {0,  -1},
              {0,  1}};

int main() {
    int L;
    cin >> L;
    int table[N][N];
    queue<Point> q;
    for (int i = 1; i <= L; ++i) {
        for (int j = 1; j <= L; ++j) {
            cin >> table[i][j];
            if (table[i][j] == 1)
                q.push(Point{i, j});
        }
    }

    int count = 0;
    while (true) {
        queue<Point> qNew;
        while (!q.empty()) {
            Point point = q.front();
            q.pop();
            for (const Point &d:ds) {
                int x = point.X + d.X;
                int y = point.Y + d.Y;
                if (1 <= x && x <= L
                    && 1 <= y && y <= L) {
                    switch (table[x][y]) {
                        case 0:
                            table[x][y] = 1;
                            qNew.push(Point{x, y});
                            break;
                        case 1:
                        case 2:
                            break;
                    }
                }
            }
        }
        if (qNew.empty()) {
            cout << count << endl;
            return 0;
        }
        ++count;
        q = qNew;
    }
}

CallMeInk's solution

#include <iostream>

using namespace std;

int main()
{
    int l;
    int a[105][105];
    cin >> l;
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++)
            cin >> a[i][j];
    bool flag = true;
    int ans = 0;
    while (flag)
    {
        flag = false;
        ans++;
        for(int i=1;i<=l;i++)
            for(int j=1;j<=l;j++)
                if (a[i][j] == 1)
                {
                    if (i-1 >=1 && a[i-1][j] == 0) {a[i-1][j] = 3;flag = true;}
                    if (i+1 <=l && a[i+1][j] == 0) {a[i+1][j] = 3;flag = true;}
                    if (j-1 >=1 && a[i][j-1] == 0) {a[i][j-1] = 3;flag = true;}
                    if (j+1 <=l && a[i][j+1] == 0) {a[i][j+1] = 3;flag = true;}
                }
        for(int i=1;i<=l;i++)
            for(int j=1;j<=l;j++)
                if (a[i][j] == 3) a[i][j] = 1;
        //cout << "flag =" << flag << endl;
        //cout << "ans =" << ans <<endl;
        //for(int i=1;i<=l;i++)
        //{
        //    for(int j=1;j<=l;j++) cout << a[i][j] << ' ';
        //    cout << endl;
        //}
    }
    ans--;
    cout << ans << endl;
    return 0;
}

FineArtz's solution

/* 二哥养细菌 */
#include <iostream>
#include <deque>
using namespace std;

int a[105][105], l;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int bfs(){
    int ans = 0;
    deque<int> nowx, nowy;
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= l; ++j)
            if (a[i][j] == 1){
                nowx.push_back(i);
                nowy.push_back(j);
            }
    while (!nowx.empty()){
        ++ans;
        int len = nowx.size();
        for (int nowc = 0; nowc < len; ++nowc){
            for (int d = 0; d < 4; ++d){
                int x = nowx[nowc] + dx[d];
                int y = nowy[nowc] + dy[d];
                if (a[x][y] == 0){
                    a[x][y] = 1;
                    nowx.push_back(x);
                    nowy.push_back(y);
                }
            }
        }
        for (int i = 1; i <= len; ++i){
            nowx.pop_front();
            nowy.pop_front();
        }
    }
    return ans - 1;
}
int main(){
    cin >> l;
    for (int i = 0; i <= 104; ++i)
        for (int j = 0; j <= 104; ++j)
            a[i][j] = 2;
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= l; ++j)
            cin >> a[i][j];
    cout << bfs() << endl;
    return 0;
}

ligongzzz's solution

#include <cstdio>
#include <iostream>

using namespace std;

//培养皿边长
int L = 0;
//模拟培养皿
int plate[101][101] = { 0 };
//上一轮结束时的繁殖结果
int _plate[101][101] = { 0 };
//空白格子数
int blank = 0;
//繁殖轮数
int turns = 0;
//判断该位置是否为空格
int judge(int i, int j) {
    if (i >= 0 && i < L && j >= 0 && j < L) {
        if (_plate[i][j] == 0 && plate[i][j] == 0) {
            plate[i][j] = 1;
            return 1;
        }
    }
    return 0;
}
//增殖
void multiply() {
    while (blank > 0) {
        for (int i = 0; i < L; ++i) {
            for (int j = 0; j < L; ++j) {
                if (_plate[i][j] == 1) {
                    blank -= judge(i + 1, j);
                    blank -= judge(i, j + 1);
                    blank -= judge(i - 1, j);
                    blank -= judge(i, j - 1);
                }
            }
        }
        for (int i = 0; i < L; ++i) {
            for (int j = 0; j < L; ++j) {
                _plate[i][j] = plate[i][j];
            }
        }
        turns++;
    }
    return;
}

int main() {
    scanf("%d", &L);
    for (int i = 0; i < L; ++i) {
        for (int j = 0; j < L; ++j) {
            scanf("%d", &plate[i][j]);
            _plate[i][j] = plate[i][j];
            if (plate[i][j] == 0)
                blank++;
        }
    }

    multiply();
    printf("%d", turns);
    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

int cal(int);

int **pet;

int main() {
    int n, sum;
    cin >> n;

    pet = new int *[n + 2];

    for (int i = 0; i < n + 2; i++) {
        pet[i] = new int[n + 2];
    }

    for (int i = 0; i < n + 2; i++) {
        pet[0][i] = -1;
        pet[n + 1][i] = -1;
        pet[i][0] = -1;
        pet[i][n + 1] = -1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> pet[i][j];
        }
    }
    sum = cal(n);

    cout << sum;

    for (int i = 0; i < n + 2; i++) {
        delete[] pet[i];
    }
    delete[] pet;
}

int cal(int n) {
    int sum = 0;
    bool isFilled = 0;

    while (isFilled != 1) {
        sum++;
        isFilled = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (pet[i][j] == 1) {
                    if (pet[i][j - 1] == 0) {
                        isFilled = 0;
                        pet[i][j - 1] = -2;
                    }
                    if (pet[i][j + 1] == 0) {
                        isFilled = 0;
                        pet[i][j + 1] = -2;
                    }
                    if (pet[i - 1][j] == 0) {
                        isFilled = 0;
                        pet[i - 1][j] = -2;
                    }
                    if (pet[i + 1][j] == 0) {
                        isFilled = 0;
                        pet[i + 1][j] = -2;
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (pet[i][j] == -2) {
                    pet[i][j] = 1;
                }
            }
        }
    }

    sum--;

    return sum;
}

skyzh's solution

#include <iostream>
using namespace std;

int now_map[2][100][100];

#define check_fill(x, y) if ((x) >= 0 && (y) >= 0 && \
                             (x) < N && (y) < N && now_map[next][(x)][(y)] != 2)

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> now_map[0][i][j];
            now_map[1][i][j] = now_map[0][i][j];
        }
    }
    int cur = 0;
    int cnt = 0;
    while (true) {
        bool end = true;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (now_map[cur][i][j] == 0) {
                    end = false;
                    break;
                }
                // cout << now_map[cur][i][j] << " ";
            }
            // cout << endl;
            if (!end) break;
        }
        if (end) break;
        int next = (cur + 1) % 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (now_map[cur][i][j] == 1) {
                    now_map[next][i][j] = 1;
                    check_fill(i - 1, j) now_map[next][i - 1][j] = 1;
                    now_map[next][i][j] = 1;
                    check_fill(i + 1, j) now_map[next][i + 1][j] = 1;
                    now_map[next][i][j] = 1;
                    check_fill(i, j + 1) now_map[next][i][j + 1] = 1;
                    now_map[next][i][j] = 1;
                    check_fill(i, j - 1) now_map[next][i][j - 1] = 1;
                }
            }
        }
        cur = next;
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

yyong119's solution

#include <iostream>
int l,i,j,rest,x,y,head,tail,times;
int map[101][101],dir[5][3],line[200][10001][3];
int main(){
    using namespace std;
    dir[1][2]=1; dir[2][2]=-1; dir[3][1]=1; dir[4][1]=-1;
    cin>>l; rest=l*l;
    for (i=1; i<=l; i++)
        for (j=1; j<=l; j++){
            cin>>map[i][j];
            if (map[i][j]) rest--;
            if (map[i][j]==1){
                tail++;
                line[times][tail][1]=i; line[times][tail][2]=j;
            }
        }
    line[times][0][0]=tail;
    while (rest){
        times++; tail=0;
        for (head=1; head<=line[times-1][0][0]; head++)
        for (i=1; i<=4; i++){
            x=line[times-1][head][1]+dir[i][1]; 
            y=line[times-1][head][2]+dir[i][2];
            if ((map[x][y]==0)&&(x>=1)&&(x<=l)&&(y>=1)&&(y<=l)){
                tail++; line[times][tail][1]=x; line[times][tail][2]=y;
                map[x][y]=1; rest--;
            }
        }
        line[times][0][0]=tail;
    }
    cout<<times;
    return 0;
}