東京理科大学 infoserv［更新日］2001.11.05

問１０

　次の C プログラムの説明及びプログラムを読んで，設問 1 〜 4 に答えよ。

〔プログラムの説明〕

迷路を解くプログラムである。

(1)　図 1 に示したような縦 8 行横 8 列の目上に表現された迷路図のデータが 2 次元配列 M に格納されている。 灰色に塗りつぶされている升が迷路の壁を示しており，白色の升が道を示している。

(2)　入口の升には始点を示すコード（0xf0）が，出口の升には終点を示すコード（0xf1）が，道の升には道を示すコード（0x00）が，壁の升には壁を示すコード（0xff ）が
格納されている。

図１　迷路の例

(3)　迷路の外周となる升（M の横座標又は縦座標が 0 又は 7 である升）は，始点と終点を除いてすべて壁である。

(4)　このプログラムで使用している大域変数の用途は，次のとおりである。

変数名

用途

M

 迷路図データの格納域（2 次元配列）

x

 迷路探索中の升の横座標

y

 迷路探索中の升の縦座標

dir

 迷路探索時の進行方向

これらの大域変数に初期値を設定し，関数 maze を呼び出すことによって 迷路を探索し，入口から出口までの道筋を求める。

〔プログラム〕

（行番号）


 1 #define   UP        0
 2 #define   RIGHT     1
 3 #define   DOWN      2
 4 #define   LEFT      3
 5 #define   ROAD      0x00             /* 道のコード */
 6 #define   WALL      0xff             /* 壁のコード */
 7 #define   SMAX      8
 8 #define   ENTRANCE  0xf0             /* 始点のコード */
 9 #define   EXIT      0xf1             /* 終点のコード */
10
11 int rcheck(void);
12 int fcheck(void);
13 void go(void);
14 void maze(void);
15
16 int M[SMAX][SMAX], x, y, dir;
17
18 void maze()
19 {
20     while ( M[y][x] != EXIT ) {
21         if ( ( rcheck() == ROAD ) ||
22              ( rcheck() == EXIT ) ) {
23             dir = ( dir+1 ) % 4;
24             go();
25         }
26         else if ( ( fcheck() == ROAD ) ||
27                   ( fcheck() == EXIT ) ) go();
28         else dir = ( dir+3 ) % 4;
29     }
30     return;
31 }
32 
33 int rcheck()
34 {
35     if      ( dir == UP )     return M[y][x+1];
36     else if ( dir == RIGHT )  return M[y+1][x];
37     else if ( dir == DOWN )   return M[y][x-1];
38     else                      return M[y-1][x];
39 }
40
41 int fcheck()
42 {
43     if      ( dir == UP )     return M[y-1][x];
44     else if ( dir == RIGHT )  return M[y][x+1];
45     else if ( dir == DOWN )   return M[y+1][x];
46     else                      return M[y][x-1];
47 }
48 
49 void go()
50 {
51     if      ( dir == UP )    y--;
52     else if ( dir == RIGHT ) x++;
53     else if ( dir == DOWN )  y++;
54     else                     x--;
55 }

設問１ 　図 2 に示す迷路を，このプログラムによって解いた道筋として正しい答えを， 解答群の中から選べ。図中の 〜 は，升の位置を示している。 ここで，関数 maze を呼び出すときの大域変数 x，y，dir の値は次のとおりとする。

x = 1
y = 0
dir = DOWN

図２　迷路の升の位置

解答群

ア　始点 → → → → → → → → → 終点

イ　始点 → → → → → → → → → → → → → 終点

ウ　始点 → → → → → 終点

エ　始点 → → → → → → → → → → → 終点

設問２ 　図 3 に示す迷路の場合，探索の道筋に関する記述として正しい答えを，解答群の中から選べ。 ここで，関数 maze を呼び出すときの大域変数 x，y，dir の値は次のとおりとする。

x = 1
y = 0
dir = DOWN

図３　閉じた迷路

解答群

ア　始点 → → → → → → → → → … を無限に繰り返す。

イ　始点 → → → → → → → → → … を無限に繰り返す。

ウ　始点 → → → → → … を無限に繰り返す。

エ　始点 → → → → → → 始点（プログラム終了)

オ　始点 → → → → → → → → … を無限に繰り返す。

設問３ 　始点及び終点を含めて，通過した升の位置と進行方向を 記録するために，プログラム中に次の文を追加することにした。 文を追加する適切な位置を解答群の中から選べ。
　なお，プログラムの先頭に #include <stdio.h> があるものとする。

printf("dir=%d y=%d x=%d\n", dir, y, x);

解答群

ア　行番号 20 の直後と行番号 29 の直後

イ　行番号 23 の直後と行番号 29 の直後

ウ　行番号 28 の直後と行番号 29 の直後

設問４ 　迷路の解法として，関数 rcheck の代わりに， 次の関数 lcheck を使用することにした。 行番号 11，21 及び 22 での関数 rcheck を lcheck に置き換える。

　その場合，プログラム中で更に変更すべき箇所として正しい答えを， 解答群の中から選べ。 

int lcheck()
{
    if      ( dir == UP )     return M[y][x-1];
    else if ( dir == RIGHT )  return M[y-1][x];
    else if ( dir == DOWN )   return M[y][x+1];
    else                      return M[y+1][x];
}

解答群

ア　行番号 21 の == ROAD を == WALL に変更する。

イ　行番号 23 の +1 を +3 に，行番号 28 の +3 を +1 に変更する。

ウ　行番号 35 及び行番号 43 の UP を RIGHT に，行番号 36 及び行番号 44 の RIGHTを DOWN に，行番号 37 及び行番号 45 の DOWN を LEFT に変更する。

エ　行番号 51 から行番号 54 までの間にある -- を ++ に，++ を -- に変更する。

東京理科大学 infoserv 戻る 次頁：問11