アルゴリズムの腐ったミカン

次に分かち合うのはleetcodeからの簡単なアルゴリズム問題です.一緒に成長しましょう.使用言語:JavaScript
説明:キュー+多源広度検索に使用する
テーマ://994.腐ったみかん/与えられたグリッド内の各セルには、次の3つの値の一つがあります.
//値0は空のセルを表します./値1は新鮮なみかんを表します.値2は腐ったみかんのことです.毎分、腐ったミカン(4つの正方形の上)に隣接する新鮮なミカンはいずれも腐敗します.セルの中に新鮮なみかんがないまでの最小分数を返します.可能でない場合は、-1を返します.
//例1:/入力:[[2,1,1],[1,1,0],[0,1,1]///出力:4
//例2://入力:[[2,1,1]、[0,1]、[1,0,1]]///////出力:-1//解釈:左下のみかん(2行目、0列目)は永遠に腐りません.腐っているので4つの順方向だけに発生します.
//例3://入力:[[0,2]///出力:0/解釈:0分で新鮮なみかんがなくなったので、答えは0です.
//ヒント://1<=grid.length<=10/1<=grid[0].length<=10/grid[i]、[j]は0、1、または2だけです.
簡単版:

function orangesRotting1(grid) {
	if(grid == 0 || grid.length == 0) return 0;
	var minute = 1;
	var flag = true;
	var r = grid.length;
	var c = grid[0].length;
	var note = new Array(r);

	for(var i = 0; i < r; i ++) {
		note[i] = new Array(c);
		for(var j = 0; j < c; j ++) {
			if(grid[i][j] == 2) {
				note[i][j] = minute;
			} else {
				note[i][j] = 0;
			}
		}
	}

	while(flag) {
		flag = false;
		for(var i = 0; i < r; i ++) {
			for(var j = 0; j < c; j ++) {
				if(grid[i][j] == 2 && note[i][j] == minute) {
					// console.log(i, j)
					if(i > 0 && grid[i - 1][j] == 1) {
						grid[i - 1][j] = 2;
						note[i - 1][j] = minute + 1;
						flag = true;
					}
					if(i < r - 1 && grid[i + 1][j] == 1) {
						grid[i + 1][j] = 2;
						note[i + 1][j] = minute + 1;
						flag = true;
					}

					if(j > 0 && grid[i][j - 1] == 1) {
						grid[i][j - 1] = 2;
						note[i][j - 1] = minute + 1;
						flag = true;
					}
					if(j < c - 1 && grid[i][j + 1] == 1) {
						grid[i][j + 1] = 2;
						note[i][j + 1] = minute + 1;
						flag = true;
					}
				}
			}
		}

		flag && minute ++;
		// console.log(note);
	}

	for(var i = 0; i < r; i ++) {
		for(var j = 0; j < c; j ++) {
			if(grid[i][j] == 1) {
				return -1;
			}
		}
	}
	return minute - 1;
}

まず腐ったミカンを全部探して、彼らを一列に並べて保存して、列の中から一つを押して取り出して、それによって列の中から取り出した腐ったミカンをもとにして、その周り(周囲の指:上下左右)に新鮮なみかんがあるかどうかを判断します.もしあれば、これらの新鮮なみかんを腐らせます.そして、新しく腐ったみかんを列の中に預けて、列からみかんを取って、その周りに新鮮なみかんがあるかどうかを判断します.
皆さんはきっと疑問がありますか?1.多源広度検索の多源はどこで体現されていますか?私たちは初めて検索した時について腐ったみかんを全部列に入れました.これらの初めて検索したみかんは最初の源です.もしいくつかあったら、多源です.そしてこれらのソースは同じ階にあります.
2.あなたは列を使っていますが、毎回腐ったミカンを取り出して、どうして同時に周りの新鮮なミカンを腐らせますか?列の特徴の一つは先に出て、私たちが初めて探したみかんは全部列の先頭に並びました.列の中で一番目のみかんは新鮮なみかんを汚染した後、このみかんを列の中から取り除いて、新しく腐ったみかんを列の最後に入れて、列の中の一番目のみかんを取って、その周りの新鮮なみかんを腐らせて、順番に類推します.初めて検索した腐ったミカンの汚染が終わった後に、第二陣の腐ったミカンだけが周りの新鮮なミカンを汚染します.
第二に、ここでは同じ時刻を指していますが、コード実行においては同じ時間帯を理解したほうがいいです.第一の時間帯に、列の中の第一陣の腐ったミカンは周りの新鮮なミカンを汚染します.第二の時間帯は、列の中の第二の腐ったミカンが周りの新鮮なみかんを汚染します.順番に類推して、腐ったミカンが周りの新鮮なみかんを汚染し終わったら、チームの頭から取り除かれます.列が空いている時には、汚染が完了します.
そして私たちは新鮮なみかんがあるかどうかを判断しています.
3.では、私たちはどのようにしてその汚染を全部記録しますか?新鮮なみかんは何分かかりますか?答:私たちはmapオブジェクトを使用することができますが、腐ったミカンの配列内の位置とどの時間(つまり何分目)で汚染された形成とは常に対応しています.腐ったみかん(Aという)が新鮮なみかん(Bといいます)を汚染したら、Bの位置に対応する時間帯はAの時間帯に1を加えます.その後、私たちはみかんが汚染されています.記録して、時間帯の最大値を比較します.

function orangesRotting2(grid) {
	if(grid == null || grid.length == 0) return -1;
	//            （    ）
	// eg: [2, 3]      
	//         [2, 4],[2, 1],[1, 3],[3, 3]             
	var a = [-1, 0, 1, 0];
	var b = [0, -1, 0, 1]; 

	var ans = 0;
	var r = grid.length;
	var c = grid[0].length;
	var map = new Map();
	var queue = new Array();

	for(var i = 0; i < r; i ++) {
		for(var j = 0; j < c; j ++) {
			if(grid[i][j] == 2) {
				var code = i * c + j;
				//              
				queue.push(code);
				map.set(code, 0);
			}
		}
	}
	

	while(queue.length != 0) {
		//            
		var code = queue.shift();
		//           
		i = Math.floor(code / c);
		j = code % c;

		for(var k = 0; k < 4; k ++) {
			//            
			var nI = i + a[k];
			var nJ = j + b[k];

			if(nI < r && nI >= 0 && nJ >= 0 && nJ < c && grid[nI][nJ] == 1) {
				//        
				grid[nI][nJ] = 2;
				var ncode = nI * c + nJ;
				//             
				queue.push(ncode);
				map.set(ncode, map.get(code) + 1);
				ans = map.get(ncode) > ans ? map.get(ncode) : ans;
			}
		}
		
	}

	//            
	for(var i = 0; i < r; i ++) {
		for(var j = 0; j < c; j ++) {
			if(grid[i][j] == 1) {
				return -1
			}
		}
	}
	return ans;

}

基本的な考え方:1.腐ったみかんを探しながら、新鮮なみかんの数を探して、腐ったみかんを列の中に入れておきます.2.この列を通して、nextQueの列を宣言します.2回目の腐ったみかんを保存します.1回目の腐ったミカンを新鮮なみかんを汚染して、汚染されたみかんをnextQueに保存します.そして、新鮮なみかんの個数を1つ減らして、最初の腐ったミカンを汚染なしに完成したら、nextQueの中の腐ったミカンを最初の列にあげて、この列を巡回して、この列に値がないまで操作します.
最後に、新鮮なみかんの数が0であるかどうかを判断します.

function orangesRotting(grid) {
	if(grid == null || grid.length == 0 || grid[0].length == 0) return -1;
	const a = [0, 1, 0, -1];
	const b = [1, 0, -1, 0];

	let minute = 0;
	let fresh = 0;
	const R = grid.length;
	const C = grid[0].length;
	let queue = [];
	

	for(let r = 0; r < R; r ++) {
		for(let c = 0; c < C; c ++) {
			if(grid[r][c] == 2) {
				queue.push([r, c]);
			} else if(grid[r][c] == 1){
				fresh ++;
			}
		}
	}

	while(queue.length != 0 && fresh) {
		let nextQueue = [];
		while(queue.length != 0) {
			let badOrange = queue.shift();
			for(let k = 0; k < 4; k ++) {
				let i = badOrange[0] + a[k];
				let j = badOrange[1] + b[k];
				if(i >= 0 && i < R && j >= 0 && j < C && grid[i][j] == 1) {
					grid[i][j] = 2;
					nextQueue.push([i, j]);
					fresh --;
				}
			}
		}
		minute ++;
		queue = nextQueue;
	}
	return fresh == 0 ? minute : -1; 
}

もしこの文章に何か間違いがあったら、直ちに指摘してください.私達は一緒に成長し、一緒に進歩します.ありがとうございます.