答案——腐烂的橘子算法题目

2019-03-15 admin

题目要求请戳

假如一个_M_ x M 格子的盒子里有 nn > 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 + 1x - 1x + Mx - 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)); 

[转载]原文链接:https://segmentfault.com/a/1190000018511353

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-57741.html

文章标题:答案——腐烂的橘子算法题目

相关文章
10个强大的纯CSS3动画案例分享
我们的网页外观主要由CSS控制,编写CSS代码可以任意改变我们的网页布局以及网页内容的样式。CSS3的出现,更是可以让网页增添了不少动画元素,让我们的网页变得更加生动有趣,并且更易于交互。本文分享了10个非常炫酷的CSS3动画案例,希望大家...
2015-11-16
从2014年的发展来展望JS的未来将会如何
&lt;font face=&quot;寰�杞�闆呴粦, Arial, sans-serif &quot;&gt;2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
12个你未必知道的CSS小知识
虽然CSS并不是一种很复杂的技术,但就算你是一个使用CSS多年的高手,仍然会有很多CSS用法/属性/属性值你从来没使用过,甚至从来没听说过。 1.CSS的color属性并非只能用于文本显示 对于CSS的color属性,相信所有Web开发人员...
2015-11-12
v-charts | 饿了么团队开源的基于 Vue 和 ECharts 的图表工具
在使用echarts生成图表时,经常需要做繁琐的数据类型转化、修改复杂的配置项,v-charts的出现正是为了解决这个 痛点。基于Vue2.0和echarts封装的v-charts图表组件,只需要统一提供一种对前后端都友好的数据格式 设置简...
2018-05-24
ajax为什么令人惊异?ajax的优缺点
使用Ajax的最大优点,就是能在不更新整个页面的前提下维护数据。这使得Web应用程序更为迅捷地回应用户动作,并避免了在网络上发送那些没有改变的信息。 Ajax不需要任何浏览器插件,但需要用户允许JavaScript在浏览器上执行。就像DHT...
2015-11-12
HTML5的5个不错的开发工具推荐
HTML5规范终于在今年正式定稿,对于从事多年HTML5开发的人员来说绝对是一个重大新闻。数字天堂董事长,DCloud CEO王安也发表了文章,从开发者和用户两个角度分析了HTML对两个人群的优势。其实,关于HTML5的开发工具,我们以往的...
2015-11-12
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
AJAX的浏览器支持
AJAX 的要点是 XMLHttpRequest 对象。 不同的浏览器创建 XMLHttpRequest 对象的方法是有差异的。 IE 浏览器使用 ActiveXObject,而其他的浏览器使用名为 XMLHttpRequest 的 Jav...
2015-11-12
typeof、instanceof和contructor的区别
typeof:以字符串的形式返回变量的原始类型,typeof在两种情况下会返回&quot;undefined&quot;:一个变量没有被声明的时候,和一个变量的值是undefined的时候,注意,typeof null也会返回object,...
2015-11-12
JavaScript的组成
一个完整的JavaScript由3个部分组成:核心(ECMAScript) 文档对象模型(DOM) 浏览器对象模型(BOM) ECMAScript 描述了该语言的语法和基本对象 ; DOM 描述了处理网页内容的方法和接口 ; BOM 描...
2015-11-12
回到顶部