1051A New Growth Industry ACM题答案 java版

题意：

A biologist experimenting with DNA modification of bacteria has found a way to make bacterial colonies sensitive to the
surrounding population density. By changing the DNA, he is able to "program" the bacteria to respond to the varying densities in their immediate neighborhood.
一位生物学家做实验修改细菌的DNA使得细菌受它周围细菌密度的影响。通过修改DNA，他可以给细菌“编程”使得细菌对它们近邻的密度变化产生反应。
The culture dish is a square, divided into 400 smaller squares (20x20). Population in each small square is measured on a four point scale (from 0 to 3). The DNA information is represented as an array D, indexed from 0 to 15, of integer values and is interpreted as follows:
培养皿是正方形的，被分成了400个更小的正方形。每一个小块的细菌数量由0到3四个数表示。DNA的信息被放在一个数组D里，数组标号从0到15.如下解释：
In any given culture dish square, let K be the sum of that square‘s density and the densities of the four squares immediately to the left, right, above and below that square (squares outside the dish are considered to have density 0). Then, by the next day, that dish square‘s density will change by D[K] (which may be a positive, negative, or zero value). The total density cannot, however, exceed 3 nor drop below 0.
在培养皿一个给定的小正方形里，设K是该小正方形的密度，和紧邻着它的上下左右四个小正方形密度的和（培养皿外面的密度被认为是0）。接着，第二天，这个小正方形里的密度会按照D[K]改变（D[K]可能是正的，负的或者0）.但最终小正方形里的密度不会超过3或者低于0.
Now, clearly, some DNA programs cause all the bacteria to die off (e.g., [-3, -3, ..., -3]). Others result in immediate population explosions (e.g., [3,3,3, ..., 3]), and others are just plain boring (e.g., [0, 0, ... 0]). The biologist is interested in how some of the less obvious DNA programs might behave.
现在很明显，一些DNA程序导致细菌死光（比如[-3, -3, ..., -3]）。还有一些导致细菌数量激增（比如 [3,3,3, ..., 3]），另外一些不会引起什么变化（比如 [0,0,0, ..., 0]）。生物学家想知道一些并不明显的DNA程序会带来怎样的影响。
Write a program to simulate the culture growth, reading in the number of days to be simulated, the DNA rules, and the initial population densities of the dish.
写一个程序模拟这些变化，读入需要模拟的天数，DNA规则和培养皿中细菌初始的密度。

思路：这个题卡了很久，本来在自己电脑上测试怎么测怎么对，但是提交就是wrong answer。走了很多弯路，还是没成功，就搜了网上的答案。看到自己的思路就是对的。但是人家高明的地方在于计算K，在我的程序中我用sum表示的，也就是五个小正方形的密度和。本来我只用了20*20的数组来放各小正方形的密度。所以计算的时候需要分开考虑 在边上和在角上的小正方形，在我的程序中计算sum分了i=0,j!=0且j<19等多种情况。当时还觉得自己考虑仔细，但是看到那位作者直接用了22*22的数组，这样边上和角上不用分开考虑，按这样提交，accepted！可能我那个分的情况太多，不知哪里还是有漏洞。。。所以ACm题要好好思考。。。。。

那位作者的链接http://blog.csdn.net/wankaiming/article/details/8104857   他用的c++

import java.util.Scanner;

public class ANewGrowth1051 {
static int sum = 0;// the sum of that square‘s density and the densities of
// the four squares immediately to the left, right,
// above and below that square
static int[][] ini = new int[22][22];// 每个小方块中的密度
static int num = 1;// 需要模拟的次数，默认为1
static int days = 0;// 要模拟的天数

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int[] arrayD = new int[16];// DNA information
num = sc.nextInt();

for (int i = 0; i < num; i++) {
days = sc.nextInt();// 读入天数
for (int j = 0; j < 16; j++)
// 读入DNA information
arrayD[j] = sc.nextInt();
for (int k = 1; k < 21; k++)
// 读取初始密度
for (int m = 1; m < 21; m++)
ini[k][m] = sc.nextInt();
for (int z = 0; z < days; z++) {
calculate(arrayD);
}

for (int x = 1; x < 21; x++) {
for (int y = 1; y < 21; y++) {
if (ini[x][y] == 0)
System.out.print(".");
else if (ini[x][y] == 1)
System.out.print("!");
else if (ini[x][y] == 2)
System.out.print("X");
else if (ini[x][y] == 3)
System.out.print("#");
}
System.out.println();
}
if (i < num - 1)
System.out.println();
}

}

public static void calculate(int[] arrayD) {
int[][] then = new int[22][22];

for (int i = 1; i < 21; i++) {
for (int j = 1; j < 21; j++) {
sum = ini[i - 1][j] + ini[i + 1][j] + ini[i][j - 1]
+ ini[i][j + 1] + ini[i][j];// 计算sum

then[i][j] = ini[i][j] + arrayD[sum];//之所以用到then[][]是因为后面的计算需要用到前面的密度，所以算出来之后不能马上改变密度值，先放在then里面
if (then[i][j] < 0)//不能低于0或者超过3
then[i][j] = 0;
if (then[i][j] > 3)
then[i][j] = 3;

}
}
ini = then;
}

}