1003. 二哥养细菌

http://acm.sjtu.edu.cn/OnlineJudge/problem/1003

类似BFS扩展的思想：

将第一代细菌位置入队列；

队列中细菌到上下左右没有细菌的位置进行繁殖、更改这些位置的标记（0->1），繁殖出的新一代细菌入栈；

如果栈空，结束，否则队列清空，栈中的新一代细菌入队列；

如果栈空，说明培养皿已经充满了（题目保证最终能够充满培养皿）。

复杂度O（n）。

# include <stdio.h>

# define N 105

int A[N][N], L;
int m;

const int d[][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};

int x[N*N], y[N*N], top;
int s[N*N], t[N*N], cnt;

int main()
{
 //  freopen("in.txt", "r", stdin);

    scanf("%d", &L);
    top = 0;
    for (int i = 1; i <= L; ++i) {
        for (int j = 1; j <= L; ++j) {
            scanf("%d", &A[i][j]);
            if (A[i][j] == 1) {
                x[top] = i;
                y[top] = j;
                ++top;
            }
        }
    }

    m = 0;
    while (1) {
        cnt = 0;
        for (int i = 0; i < top; ++i) {
            for (int j = 0; j < 4; ++j) {
                int nx = x[i]+d[j][0];
                int ny = y[i]+d[j][1];
                if (0>=nx||nx>L||0>=ny||ny>L) continue;
                if (A[nx][ny] == 0) {
                    s[cnt] = nx;
                    t[cnt] = ny;
                    ++cnt;
                    A[nx][ny] = 1;
                }
            }
        }
        if(cnt <= 0) break;
        for (int i = 0; i < cnt; ++i) {
            x[i] = s[i];
            y[i] = t[i];
        }
        top = cnt;
        ++m;
    }

    printf("%d
", m);

    return 0;
}