二哥养细菌 - 一道c++题目，帮忙看下小弟我的代码哪里有有关问题

2013-06-26

二哥养细菌 ---- 一道c++题目，帮忙看下我的代码哪里有问题？题目描述二哥不仅种苹果和花生，还养了很多细菌。

二哥养细菌 ---- 一道c++题目，帮忙看下我的代码哪里有问题？
题目描述

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

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

输入格式
第1行有1个整数，边长L。

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

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

说明

样例解释：

第一轮繁殖：

第二轮繁殖：

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

Sample Input

Sample Output
2

我的代码如下，但是答案不对，求指导哪些地方出错了？感激不尽！


#include<iostream>
#include<cstring>
using namespace std;

int L,i,j;
bool flag=false;
int m=0;
int cell[100][100];
bool mark[100][100];

int main()
{
cin>>L;

for (i=0;i<L;i++)
  for (j=0;j<L;j++)
    cin>>cell[i][j];
    
while(!flag)
{
for (i=0;i<L;i++)
  for (j=0;j<L;j++)
      {
        if (cell[i][j]==1&&i>0&&j>0&&i<L-1&&j<L-1)
          {(cell[i-1][j]!=2)?cell[i-1][j]=1:0;
           (cell[i+1][j]!=2)?cell[i+1][j]=1:0;
           (cell[i][j-1]!=2)?cell[i][j-1]=1:0;
           (cell[i][j+1]!=2)?cell[i][j+1]=1:0;
           
          }
        else if (cell[i][j]==1&&i==0&&j>0&&j<L-1)
          {(cell[i+1][j]!=2)?cell[i+1][j]=1:0;
           (cell[i][j-1]!=2)?cell[i][j-1]=1:0;
           (cell[i][j+1]!=2)?cell[i][j+1]=1:0;
           
          }
        else if (cell[i][j]==1&&i>0&&j==0&&i<L-1)
   {(cell[i-1][j]!=2)?cell[i-1][j]=1:0;
(cell[i+1][j]!=2)?cell[i+1][j]=1:0;
(cell[i][j+1]!=2)?cell[i][j+1]=1:0;

               }
            else if (cell[i][j]==1&&i==L-1&&j>0&&j<L-1)
              {(cell[i-1][j]!=2)?cell[i-1][j]=1:0;
           (cell[i][j-1]!=2)?cell[i][j-1]=1:0;
           (cell[i][j+1]!=2)?cell[i][j+1]=1:0; 
 
           
          }
        else if (cell[i][j]==1&&i>0&&j==L-1&&i<L-1)
          {(cell[i-1][j]!=2)?cell[i-1][j]=1:0;
           (cell[i+1][j]!=2)?cell[i+1][j]=1:0;
           (cell[i][j-1]!=2)?cell[i][j-1]=1:0;
           
          }
        else if (cell[i][j]==1&&i==0&&j==0)
          {
           (cell[i+1][j]!=2)?cell[i+1][j]=1:0;
           (cell[i][j+1]!=2)?cell[i][j+1]=1:0;
           
          }
        else if (cell[i][j]==1&&i==0&&j==L-1)
          {(cell[i+1][j]!=2)?cell[i+1][j]=1:0;
           (cell[i][j-1]!=2)?cell[i][j-1]=1:0;
           
          }
        else if (cell[i][j]==1&&i==L-1&&j==0)
          {(cell[i-1][j]!=2)?cell[i-1][j]=1:0;
           (cell[i][j+1]!=2)?cell[i][j+1]=1:0;
          
          }
        else if (cell[i][j]==1&&i==L-1&&j==L-1)
          {(cell[i-1][j]!=2)?cell[i-1][j]=1:0;           
           (cell[i][j-1]!=2)?cell[i][j-1]=1:0;
           
          }
        if (cell[i][j]==1||cell[i][j]==2) mark[i][j]=true;
     
 }
   for (i=0;i<L;i++)
  for (j=0;j<L;j++)
   if (mark[i][j]) flag=true;
  
m=m+1;
    }
    cout<<m;
 
}

C++
[解决办法]
你这段代码还有一个问题，如果最开始时所有格子都有细菌或抗生素，天数应该是0，但这段代码m至少是一。

其实不需要mark数组，在while开始时把flag设为true,当有格子发生改变时（从0变1）设为false就行了。然后m最后要减一，因为最后一次什么都没做。

此外，如果细菌被抗生素包围，这段代码会是无限循环。

这道题我考虑用递归去做，用一个同样大小的天数矩阵：
1：初始化天数矩阵，有细菌为0，无细菌为-1，有抗生素为-2.

2：对于每个格子，如果value>= 0 则：
    2.1：对于当前格子的所有相邻格子，如果其值不为-2，并且>value + 1,则：
       2.1.1：该相邻格子值设为value+1;
       2.1.2：对该相邻格子作步骤2。
3：检查天数矩阵，如果有-1元素存在，则无解；否则计算天数矩阵中的元素最大值。
[解决办法]
就一个简单的BFS。。首先把所有1的点放进队列。。然后不断从队列中取点向四周扩展。。直到扩满为止。。看看那天是多少天就可以了。。
[解决办法]

引用:

要区分出哪些是刚被繁殖的，可以先用其他值，一轮繁殖后再替换成1

最容易想到的，丝毫没有任何算法的做法：


#include<stdio.h>
#include<stdlib.h>

#define N (3)

int func(int a[N][N])
{
    int i, j;
    int cycle;
    int cnt = 0;
    
    //统计共有多少个可被繁殖的格子
    for (i = 0; i < N; ++i)
    {
        for (j = 0; j < N; ++j)
        {
            if (0 == a[i][j])
            {
               ++cnt;
            }
        }
    }
    
    for (cycle = 0; cnt; ++cycle)
    {
        for (i = 0; i < N; ++i)
        {
            for (j = 0; j < N; ++j)
            {
                if (0 == a[i][j])
                {
                    if ((i > 0 && (1 == a[i - 1][j])) 
[解决办法]
 
                        (i < (N - 1) && (1 == a[i + 1][j])) 
[解决办法]
 
                        (j > 0 && (1 == a[i][j - 1])) 
[解决办法]
 
                        (j < (N - 1) && (1 == a[i][j + 1])))
                    {
                        a[i][j] = -1;//刚被繁殖的使用-1来区分1 
 
                        --cnt;
                    }
                }
            }
        }
        
        //将刚被繁殖的格子替换为1
        for (i = 0; i < N; ++i)
        {
            for (j = 0; j < N; ++j)
            {
                if (-1 == a[i][j])
                {
                    a[i][j] = 1;
                }
            }
        }
    }
    
    return cycle;
}

int a[3][3] = 
{
    2, 0, 0,
    0, 1, 0,
    0, 0, 0
};

int main()
{
    printf("%d\n", func(a));
    
    system("pause");
    return 0;
}

热点排行