二番目の兄は細菌を飼っている.

http://acm.sjtu.edu.cn/OnlineJudge/problem/1003
タイトルの説明
二番目の兄はりんごと落花生だけでなく、細菌もたくさん飼っています.二兄の細菌培養皿は四角形になり、辺長はLである.長期培養後、二番目の兄は細菌の繁殖の法則を発見した:最初は各格子の中の細菌とその子孫が独立して繁殖し、繁殖するたびに上下左右の4つの隣接する格子の中で新しい細菌を産生し、すでに存在している細菌は培養皿が細菌に満ちている前に死亡しない.また、いくつかの格子には抗生物質があるかもしれませんが、細菌は抗生物質のある格子では繁殖できません.
二番目の兄は、新しい培養皿を取り、いくつかの格子に細菌や抗生物質を入れ、培養皿全体に満ちた抗生物質のない格子まで細菌が繁殖するのを観察するゲームを発明した.しかし、二番目の兄はすでにこのゲームにうんざりしていて、彼は今何回繁殖した後、細菌が培養皿全体(抗生物質の格子ではない)に満ちているか知りたいだけです.
入力フォーマット
1行目には1つの整数、辺長Lがあります.
2行目からL+1行目まで、行ごとにL個の整数があり、値は0、1または2である.0は格子に最初に細菌がいないことを示し、1は格子に最初に細菌がいたことを示し、2は格子に最初に抗生物質があったことを示した.
出力フォーマット
整数mを出力し、m輪繁殖後、細菌が培養皿全体(抗生物質のない格子)に満たされることを示す.
説明
【例の説明】第1ラウンドの繁殖:
2 1 0
1 1 1
0 1 0
第2ラウンドの繁殖:
2 1 1
1 1 1
1 1 1
【データ範囲】
全データについて:1≦L≦100 ,最終的に培養皿(抗生物質のない格子)を満たすことを保証する.
Sample Input

3
2 0 0
0 1 0
0 0 0

Sample Output

2

      遍歴のたびに元素値が1の場合、その上下左右の元素値が0の場合、遍歴時に元素値が変化しないまで対応する位置の元素値を1とし、細菌が器に満ちていることを示す.この方法の時間的複雑さは、遍歴の全過程で遍歴が繰り返され、上下左右が1要素値であるため、遍歴された要素の数は遍歴回数の増加とともに増大する.
      では、要素の重複を減らすにはどうすればいいのでしょうか.
      毎回遍歴する過程で、次に遍歴する必要がある元素の位置を決定して保存することができますか?次にこれらの保存した元素を遍歴すればいいので、遍歴する必要がない元素があるときに細菌が器に満ちているまで反復することができます.
これはいいです.
      各遍歴において、要素の値が1の場合、その対応する上下左右の値が0の場合、その対応する上下左右の要素の座標を1つの配列に記録する.すなわち、配列には、今回の遍歴で0から1になった要素、すなわち、次回遍歴した要素の位置が格納される.
      では、この配列の過去の遍歴に格納された元素の総数はL^2以下であり、器の中に抗生物質が置かれる可能性があるためである.すなわち、各要素は最大1回しか遍歴されず、時間の複雑さを大幅に低減する.
コードは次のとおりです.

#include 
#include 
using namespace std;


int main()
{
	int L;  //      
	cin>>L;
	int **p = new int*[L];     //    
	int *x = new int[L*L];     //       1       
	int *y = new int[L*L];     //       1       
	int *n_x = new int[L*L];   //          1       
	int *n_y = new int[L*L];   //          1       
	int top = 0;     //          
	int n_top = 0;   //          
	int m = 0; //      

	int i = 0, j = 0;
	for(i = 0; i < L; i++)     //           
	{
		p[i] = new int[L];
	}

	for(i = 0; i < L; i++)
	{
		for(j = 0; j < L; j++)
		{
			cin>>p[i][j];
			if(1 == p[i][j])
			{
				x[top] = i;
				y[top] = j;
				top++;
			}
		}
	}
	
	const int d[][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};
	while(1)
	{
		for(i = 0; i < top; i++)
		{
			for(j = 0 ; j < 4; j++)
			{
				int x1 = x[i]+d[j][0];
				int y1 = y[i]+d[j][1];
				

				if( 0 > x1 || x1 >= L || 0 > y1 || y1 >=L)			
					continue;
								
				if(0 == p[x1][y1])
				{
					n_x[n_top] = x1;      //             、   。
					n_y[n_top] = y1;      
					n_top++;
					p[x1][y1] = 1;
				}
			}
		}
		
		if(n_top == 0) break;
		for(i = 0; i

 時間:30 ms/メモリ:47952 kb
参照先:http://www.cnblogs.com/txd0u/p/3352328.html    
この論文では,静的配列を用い,実行時間はより速いが,要素を収容するために大きな静的配列を事前に定義し,空間的複雑さは本論文の動的配列を用いる方法よりも大きい.