第5部分流程類(工作流程和算法流程)

　　●試題1

　　閱讀以下說明和流程圖，從供選擇的答案中選出應填人流程圖(n)處的字句寫在答題紙的對應欄內。

　　【說明】

　　某游戲的地圖區域可分成n×m個方格，如圖5.1(a)所示，現在需要確定區域中給定的兩個方格的中心點之間的最短前進方案。前進路線只能沿水平或垂直方向，如圖5.1(b)中虛線所示。為了避免路線相交，應將有障礙的方格作封鎖標記，其他線路不允許穿過被封鎖的方格。

　　 

　　設給定地圖區域的起始方格a與目的方格b尚未被封鎖，求這兩個方格問最短前進方案的基本思路是：從起始方格a開始，先考查距離起始方格距離為1的可達方格并用一個路徑長度值標記，然后依次考查距離為2、3、…的可達方格，直到距離為k的某一個可達方格就是目標方格b時為止，或者由于不存在從a到b的前進方案而終止。地圖區域中的每一個方格與其相鄰的上、下、左、右四個方格之間的距離為1，依次沿下、右、上、左這四個方向考查，并用一個隊列記錄可達方格的位置。表5.1給出了沿這四個方向前進l步時相對于當前方格的相對偏移量。

　　表5.1

　　例如，設游戲的地圖區域可劃分為一個6×8的方格陣列，如圖5.2(a)所示，其中陰影表示已封鎖方格。從起始方格a(位置[3，2]，標記為0)出發，按照下、右、上、左的方向依次考查，所標記的可達方格如圖5.2(a)所示，目標方格為b(位置[4，7]，標記為10)，相應的最短前進路徑如圖5.2(b)虛線所示如圖5.3和圖5.4所示的流程圖即利用了上述思路，在地圖方格陣列中進行標記，圖中使用的主要符號見表5.2。在圖5.4中，設置地圖初始格局，即將可前進方格置為數值-1、已前進方格(即封鎖方格)置為-9。設置方格陣列“圍墻”的目的是省略方格位置的邊界條件判定，方法是在四周附加方格，并將其標記為-9(與封鎖標記相同)。