Oops周末一题（兔哥哥儿养细菌）
非常高兴又可以多一块内容了。这里非常感谢“Oops”学弟，特别说明本部分是小白的学弟“Oops”同学独家赞助。也欢迎更多的小伙伴来分享你的学习成果
兔哥哥儿养细菌
Description
兔哥哥儿不仅种苹果，还养了很多细菌。兔哥哥儿的细菌培养皿成方格形，边长为L。长期培养后，兔哥哥儿发现了细菌繁殖的规律：最初每个格子里的细菌及其后代都会独立繁殖，每次繁殖都会在其上下左右四个相邻的格子里产生新的细菌，而已经存在的细菌在培养皿充满细菌之前都不会死亡。另外，有一些格子里可能还有抗生素，细菌在有抗生素的格子里无法繁殖。
兔哥哥儿于是发明了一个游戏：取一个新的培养皿，在某些格子里放入细菌或抗生素，然后观察细菌不断繁殖直至充满整个培养皿的所有没有抗生素的格子。不过兔哥哥已经对这个游戏厌烦了，他现在只想知道经过多少轮繁殖后，细菌会充满整个培养皿（不算有抗生素的格子）。
Input Format
第1行有1个整数，边长L。
第2行至第L+1行，每行有L个整数，取值为0、1或2。
0表示格子里最初没有细菌，1表示格子里最初有细菌，2表示格子里最初有抗生素。
Output Format
输出一个整数m，表示经过m轮繁殖后，细菌会充满整个培养皿（不算有抗生素的格子）。
Sample Input
3
2 0 0
0 1 0
0 0 0
Sample Output
2
样例解释
第一轮繁殖：
2 1 0
1 1 1
0 1 0
第二轮繁殖：
2 1 1
1 1 1
1 1 1
数据范围
对于全部数据：1≤L≤100 ，保证最终能够充满培养皿（不算有抗生素的格子）。
解析
模拟+记忆化搜索（*）
这道题我卡了一会儿QAQ。
纠结在要使用什么类型的数据结构，一般优化思路是记忆化搜索：struct进行（x,y,col）三元的记录，然后通过queue的队列完成。然后因为我懒得写（划掉，是不熟练且不想用STL），后来在想怎么用普通的方法实现。其实这是一道水题，只是被优化放大了难度，算法的高效性由此体现。
70分的是一般思路的模拟，100分通过的是我用数组模拟队列（可以看到tail和head指针）完成，技巧在于col颜色记录，需要几次繁殖，也就是在当前状态的col+1和maxn取最大值就是总繁殖次数，擂台法即可。
未算法优化代码（70 points）
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int a[101][101],l;
int ch(){
int i,j;
for(i=1;i<=l;i++){
for(j=1;j<=l;j++){
if(a[i][j]==0){
return 1;
}
}
}
return -1;
}
int main(){
int i,j,t;
int ans=0;
cin>>l;
for(i=1;i<=l;i++){
for(j=1;j<=l;j++){
cin>>t;
if(t==2){
a[i][j]=-1;
}
else{
a[i][j]=t;
}
}
}
while(1){
if(ch()==-1){
break;
}
ans++;
for(i=1;i<=l;i++){
for(j=1;j<=l;j++){
if(a[i][j]==ans){
if(a[i][j+1]!=-1)a[i][j+1]=ans+1;
if(a[i][j-1]!=-1)a[i][j-1]=ans+1;
if(a[i+1][j]!=-1)a[i+1][j]=ans+1;
if(a[i-1][j]!=-1)a[i-1][j]=ans+1;
}
}
}
}
cout<<ans;
return 0;
}
算法优化代码（100 points）
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,a[101][101],maxn=1;
int x[10005],y[10005],t=1,h=1;
void f(int p){
if(a[x[p]+1][y[p]]==0){
a[x[p]+1][y[p]]=a[x[p]][y[p]]+1;
x[t]=x[p]+1;
y[t]=y[p];
t++;
if(a[x[p]][y[p]]+1>maxn)maxn=a[x[p]][y[p]]+1;
}
if(a[x[p]-1][y[p]]==0){
a[x[p]-1][y[p]]=a[x[p]][y[p]]+1;
x[t]=x[p]-1;
y[t]=y[p];
t++;
if(a[x[p]][y[p]]+1>maxn)maxn=a[x[p]][y[p]]+1;
}
if(a[x[p]][y[p]+1]==0){
a[x[p]][y[p]+1]=a[x[p]][y[p]]+1;
x[t]=x[p];
y[t]=y[p]+1;
t++;
if(a[x[p]][y[p]]+1>maxn)maxn=a[x[p]][y[p]]+1;
}
if(a[x[p]][y[p]-1]==0){
a[x[p]][y[p]-1]=a[x[p]][y[p]]+1;
x[t]=x[p];
y[t]=y[p]-1;
t++;
if(a[x[p]][y[p]]+1>maxn)maxn=a[x[p]][y[p]]+1;
}
}
void prt(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%3d",a[i][j]);
}cout<<endl;
}
}
int main(){
int i,j;
cin>>n;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]==2){
a[i][j]=-1;
}
if(a[i][j]==1){
x[t]=i;
y[t]=j;
t++;
}
}
}
for(i=0;i<=n+1;i++){
a[0][i]=-1;
a[i][0]=-1;
a[n+1][i]=-1;
a[i][n+1]=-1;
}
while(h<t){
f(h);
//prt();
h++;
}
cout<<maxn-1;
return 0;
}
相关推荐