答案——腐爛的橘子演算法題目

摘要： 題目要求請戳 假如一個M xM 格子的盒子裡有n （n > 0）個新鮮橘子，有m 個爛橘子。每隔一分鐘我們去這個盒子裡面數一數，直到爛橘子沒有增加。結果就是： 1.並且還有新鮮的橘子，返回 -1。 2.沒有新鮮的橘...

題目要求請戳

假如一個M xM 格子的盒子裡有n （n > 0）個新鮮橘子，有m 個爛橘子。每隔一分鐘我們去這個盒子裡面數一數，直到爛橘子沒有增加。結果就是：

1.並且還有新鮮的橘子，返回 -1。

2.沒有新鮮的橘子，返回分鐘數。

第一步將二維陣列初始化為一維陣列：

function initData(a){
var 
result = [],
n = 0,
m = 0,
j = 0;
for(j = 0; j < M; j++) {
result[j * M + 0] = { status: a[j][0], willBletOthers: a[j][0] === 2 };
result[j * M + 1] = { status: a[j][1], willBletOthers: a[j][1] === 2 };
result[j * M + 2] = { status: a[j][2], willBletOthers: a[j][2] === 2 };

if (a[j][0] == 1) {
n += 1;
}
if (a[j][1] == 1) {
n += 1;
}
if (a[j][2] == 1) {
n += 1;
}

if (a[j][0] == 2) {
m += 1;
}
if (a[j][1] == 2) {
m += 1;
}
if (a[j][2] == 2) {
m += 1;
}
}
return {
result: result,
n: n,
m: m
};
}

每隔一分鐘，一個放在x 位置的格子的爛橘子，其他四個位置x + 1 、x - 1 、x + M 、x - M ，都會腐爛(注意邊界)。如果這四個位置部分位置有新鮮的橘子，那麼腐爛還會繼續。然後繼續觀察其他位置，直到最後一個格子。下一分鐘再來看

function blet(index, result){
var bletNum = 0;
if(-1< index + 1 && index + 1 < M*M && result[index + 1].status == 1){
bletNum += 1;
result[index + 1] = {status: 2, willBletOthers: false}
}
if(-1< index + M && index + M < M*M && result[index + M].status == 1){
bletNum += 1;
result[index + M] = {status: 2, willBletOthers: false}
}

if(-1< index - 1 && index - 1 < M*M && result[index - 1].status == 1){
bletNum += 1;
result[index - 1] = {status: 2, willBletOthers: true}
}
if(-1< index - M && index - M < M*M && result[index - M].status == 1){
bletNum += 1;
result[index - M] = {status: 2, willBletOthers: true}
}
return bletNum;
}
var 
M = 3,
rawData = [[2, 1, 1], [1, 1, 0], [0, 1, 1]];

function letGo(rawData){
var data = initData(rawData),
result = data.result,
n = data.n,
m = data.m,
k,
mins = 0,
sum;

if(m == 0 && n > 0){
return -1;
}
if(m == 0 && n == 0){
return 0;
}
while (n > 0 && m > 0) {
mins += 1;
sum = 0;
for (k = 0; k < result.length; k++) {
if (result[k].status == 2) {
if (result[k].willBletOthers) {
sum += blet(k, result);
} else {
result[k].willBletOthers = true;
}
}
}

if (sum === 0) {
break;
} else {
n -= sum;
m += sum;
}
}

return mins;
}

console.log(letGo(rowData));