当前位置: 高中信息技术 / 综合题
  • 1. (2020高三上·浙江月考) 城堡问题。有一个城堡的地形图,城堡被分割成若干个方块,每个方块可以有 0~4 面墙(粗线表示墙)。

    每个方块用一个代表其周围墙的数字之和(0≤p≤15)表示:1 表示西墙,2 表示北墙,4 表示东墙,8 表示南墙。城堡的内墙被计算两次,方块(1,1)的南墙同时也是方块(2,1)的北墙。城堡至少有两个房间。例如,图a的每个方块对应数字如图b所示。

    图a

    图b

    程序运行界面如图c所示,现已知城堡地形对应的数字矩阵,要求出城堡一共有多少房间,最大 的房间有多大。小金利用深度优先搜索算法解决当 前问题,具体算法如下:

    图c

    在城堡中按行搜索,找到第一个未被搜索过方块, 以它为起点,分别按左、上、右、下的顺序向其四个方向试探,若发现一个方向上的方块是未被搜索过且可以通往的(无墙),则以这个方块为新起点,再重复上述试探。若当前方块四个方向上均无路可走,则返回上一个方块进行其他方向上的搜索,直至返回开始当前搜索的第一个方块且这个方块四个方向上也无路可走是,则本轮搜索结束。

    1. (1) 将界面中方块(2,2)对应的数字9改为13,方块(2,3)对应的数字6改为7,则城堡中最大的房间占块方格。
    2. (2) 实现上述功能的VB程序如下,请在划线处填入合适的代码。

      Const m = 4 Const n = 7

      Dim a(1 To m * n * 4) As Integer

      Dim f(1 To m * n) As Boolean

      Dim c(1 To m * n) As Integer

      Private Sub Command1_Click()

          Dim i As Integer, j As Integer, x As Integer, y As Integer

          Dim area As Integer, max As Integer, cnt As Integer

          '城堡地形对应的数字矩阵,存入 c 数组中,并显示在列表框 List1 中,f 数组初值为 false, 代码略

          For i = 1 To m * n

              x = c(i)

              For j = 1 To 4

                  a((i - 1) * 4 + j) = x Mod 2

                  x = x \ 2

              Next j

          Next i

          max = 0

          For i = 1 To m

              For j = 1 To n

                  IfThen

                  cnt = cnt + 1

                  area = Search(i, j)

                  If max < area Then

                      max = area

                  End If

              Next j

          Next i

          Label1.Caption = "城堡一共有" + Str(cnt) + "个房间,最大的房间占" + Str(max) + "块方格."

      End Sub

      '从方块(x, y)开始搜索,并返回其所在房间所占方块数.

      Function Search(ByVal x As Integer, ByVal y As Integer) As Integer

          Dim i As Integer, j As Integer, sum As Integer, r As Integer, c As Integer

          Dim pre(1 To m * n) As Integer     '记录当前房间搜索的路径

          Dim row(1 To 4) As Integer, col(1 To 4) As Integer

          row(1) = 0: row(2) = -1: row(3) = 0: row(4) = 1

          col(1) = -1: col(2) = 0: col(3) = 1: col(4) = 0

          sum = 1: j = 1: pre(1) = x * 10 + y

          f((x - 1) * n + y) = True

          Do While True

              For i = 1 To 4

                  r = x + row(i): c = y + col(i)

                  If r >= 1 And r <= m And c >= 1 And c <= n Then

                      If f((r - 1) * n + c) = False AndThen

                          sum = sum + 1

                          x = r: y = c

                          f((x - 1) * n + y) = True

                          j = j + 1

                          pre(j) = x * 10 + y

                          Exit For

                      End If

                  End If

              Next i

              If i > 4 Then

                 

                  If j = 0 Then

                  Exit Do

                  x = pre(j) \ 10: y = pre(j) Mod 10

              End If

          Loop

          Search = sum

      End Function

微信扫码预览、分享更方便