民科吧 关注:356,048贴子:4,848,857
  • 36回复贴,共1

初中信竞题求助:给你一个棋盘和所有雷的位置编程求出扫完这盘雷

只看楼主收藏回复

初中信竞题求助:
给你一个棋盘和所有雷的位置
编程求出扫完这盘雷所需要的最少点击数


IP属地:江苏来自手机贴吧1楼2020-05-31 11:16回复
    我怎么记得这是个典型的例题


    IP属地:北京来自Android客户端4楼2020-05-31 11:49
    收起回复
      要求复杂度是多少?


      IP属地:甘肃来自Android客户端5楼2020-05-31 14:23
      收起回复
        萌新答题,不知对错:遍历一遍,把雷的位置标为-1,雷的周围的位置标为-2(代表这里有数字),其余位置标为0(代表是空格)。然后再遍历一遍,统计值为-2的且周围没有0的有多少个。然后对空格染色,染成的块数加上面的值为-2且周围没有0的个数就是结果。。。


        IP属地:北京来自Android客户端7楼2020-05-31 17:51
        收起回复
          如果抖机灵的话直接输出1就OK了,失败也算扫完,实在的我还真得算算(oi两位数得分的水货大概率得想几天


          IP属地:辽宁来自iPhone客户端8楼2020-06-01 01:01
          回复
            35分钟才算确定了一个看起来靠谱的方法,看来我只能在济宁市第二职业中学继续我的痛苦经历了


            IP属地:辽宁来自iPhone客户端9楼2020-06-01 01:38
            回复
              四维数组表每个块的位置,标号及是否点开的状态,然后查找标号为0的,之后顺着标号为0的块查找它前后左右其他标号为0的块,并吧找到的所有标记为0块的周围块设为点开:一直循环,之后在其他未点开的标号为0的块中重复,遍历整个数组的同时重复几次就点击了几下。然后再次遍历数组,如果遇到的某个块周围未点开的块数等于其编号,直接把周围未点开的块设成标雷状态,遍历到最后之后点剩下的块(懒得考虑到底剩不剩块的问题了,深夜降智状态缺乏基本自信,也是这个暴力法想了35分钟才确定的缘故之一)应该就完工了


              IP属地:辽宁来自iPhone客户端10楼2020-06-01 01:46
              收起回复
                我觉得这个写暴力的话应该能拿七八十,但是中途有几个地方需要注意,容易死循环


                IP属地:辽宁来自iPhone客户端11楼2020-06-01 01:48
                回复
                  有点难啊。


                  IP属地:湖南来自Android客户端13楼2020-07-13 07:41
                  回复
                    我做了一下:104


                    IP属地:重庆来自Android客户端14楼2020-07-13 07:57
                    回复
                      从右上角点S型扫雷


                      IP属地:重庆来自Android客户端15楼2020-07-13 08:02
                      收起回复
                        规则太模糊,扫雷有几种点击方式。
                        标记一颗地雷算不算一次 ?
                        双击算几次点击?
                        在最极端的情况下,先标记所有地雷,一次点击就能完成一个联通区域。


                        IP属地:浙江16楼2020-07-13 12:40
                        收起回复
                          双击1可同时翻开四块。


                          IP属地:浙江17楼2020-07-26 21:53
                          收起回复

                            首先说明下,在最少点击的情况下,大多数情况下只有左键就行了,需要右键的情况极少。
                            不过少不代表没有,这图就是一个例子。
                            显然要点击左上和右下。于是能显示红色的数字。这时候右键标记中间的雷,再双击加粗的“1”,可以2键点出4个绿色的“2”。如果只用左键,是需要4次的,就少了2次点击。


                            IP属地:湖南18楼2020-07-28 09:16
                            回复