# 11003: 【原1003】二哥养细菌

### 题目描述

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

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

2 1 0

1 1 1

0 1 0

2 1 1

1 1 1

1 1 1

【数据范围】

## Sample Input

3
2 0 0
0 1 0
0 0 0


## Sample Output

2


## 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 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 (i=1; i<=4; i++){