R4秋季応用情報午後プログラミング「迷路」をPythonでコーディングしてみた！

2022-10-302022-11-06

主

こんにちは、主です！

久々の投稿になります。

最近は、アルバイトや資格試験、学会発表等多忙を極めていましたのでなかなか投稿が難しく、気づけばもう冬目前ですね。

ようやく、普通の日常が戻ってきたので就活が始まる３月くらいまでは趣味程度にブログ更新していこうかなと考えております。

では本題。

皆さんは10月9日にあった応用情報技術者試験、受験しましたか？当ブログでも度々取り上げてきた「応用情報技術者試験」ですが、春期試験を逃した（予約忘れ）僕は満を持して秋季試験を受験してまいりました。

正直、手ごたえは微妙。。。

今回は例年に比べてやや易化していたような気もしますが、普段解いていた分野を避けて別の分野を解いてしまったことが要因でしょうか。

まあ、そんなことはさておき、来月辺りから諸事情でプログラミング言語のPythonを扱う予定があってですね、その練習がてら応用情報技術者試験午後問題３の「プログラミング」をコーディングしてみよう！ということでコーディングしてみたので記録として残しておきます。

主

試験結果は結果が分かり次第ご報告します！

問題内容
プログラムコード
結果
まとめ

問題内容

問題分は長くなるので端的にまとめておきますね。

問３迷路の探索処理について

・n×mの２次元マス（迷路）を用意し、始点と終点を決めてその解路を全て見つける。

・迷路内には障害物マスが存在し、そのマスに移動することはできない。

・また、”移動”には”進む”と”戻る”の２種類存在する。障害物マスにはNGフラグ、それ以外にはOKフラグを立て、”進む”はOKフラグが立っているマスにしか進めない。

・”進む”処理を行った場合は現在いるマスに足跡フラグを立てる。

・”進む”処理には①ｙ座標を１増やす、②ｘ座標を１増やす、③ｙ座標を１減らす、④ｘ座標を１減らすの４種類存在し、①②③④の順に実行する。

・”進む”ことができない場合には”戻る”処理を行う。

・”戻る”処理は”進んで”きた１つ前のマスに動くことで、今いるマスのフラグをOKフラグに戻してから移動する。

以上を再帰的に行う。

といった感じです。（間違ってたらすみません）

詳しくは過去問をご覧ください！（R4 10/30現在ではまだ過去問の公開はされていないようです）

プログラムコード

ではプログラムを書いていきます。

ライブラリのインポート

import matplotlib.pyplot as plt
import matplotlib.patches as pat

問題にはありませんが、迷路を表示したいのでそれ用のライブラリです。

移動関数visitを作成

def visit(x, y):
    global maze
    global stack_top
    global stack_visit
    global paths
    global sol_num
    global way
    maze[x][y]=VISITED
    if (len(stack_visit) < stack_top+1):
        stack_visit.append([x, y])
    else:
        stack_visit[stack_top]=[x, y]
    if (x == goal_x and y == goal_y):
        path=[]
        for k in range(stack_top+1):
            path.append(stack_visit[k])
        #paths[sol_num]=stack_visit.copy()
        paths[sol_num]=path.copy()# Pythonは変数参照型　.copyなしでは最終的なpathの値が全てに反映される　
        sol_num=sol_num+1
    else:
        stack_top=stack_top+1
        if (maze[x][y+1] == OK):
            visit(x,y+1)
        if (maze[x+1][y] == OK):
            visit(x+1,y)
        if (maze[x][y-1] == OK):
            visit(x,y-1)
        if (maze[x-1][y] == OK):
            visit(x-1,y)
        stack_top=stack_top-1
    maze[x][y]=OK

問題文とほとんど同じものになります。

注意点として、Pythonは変数参照型なので paths[sol_num]=path ではなく、 paths[sol_num]=path.copy() とします。

メインプログラム

maze=[[0 for i in range(5)] for j in range(5)]
stack_visit=[]
point_x=[]
point_y=[]
paths={}
stack_top=0
sol_num=0
OK=1
NG=2
VISITED=3

#枠以外の好きな部分を適宜変更
maze[0][0]=NG
maze[0][1]=NG
maze[0][2]=NG
maze[0][3]=NG
maze[0][4]=NG
maze[1][0]=NG
maze[1][1]=OK
maze[1][2]=OK
maze[1][3]=OK
maze[1][4]=NG
maze[2][0]=NG
maze[2][1]=OK
maze[2][2]=OK
maze[2][3]=OK
maze[2][4]=NG
maze[3][0]=NG
maze[3][1]=OK
maze[3][2]=NG
maze[3][3]=OK
maze[3][4]=NG
maze[4][0]=NG
maze[4][1]=NG
maze[4][2]=NG
maze[4][3]=NG
maze[4][4]=NG

#始点と終点
start_x=1
start_y=1
goal_x=3
goal_y=3

#探索開始
visit(start_x,start_y)
#解を表示
if (sol_num == 0):
    print("no maze")
else:           
    for num in range(sol_num):
        print("解" + str(num+1) + "=" + str(paths[num]))

#迷路を作成
x = [0,0.2,0.4,0.6,0.8]
y = [0,0.2,0.4,0.6,0.8]
for num in range(sol_num):
    path_len=len(paths[num])
    point_x=[]
    point_y=[]
    #解路の座標
    for i in range(path_len):
        point_x.append( (float(paths[num][i][0])+float(paths[num][i][0])+1.0)*0.1 )
        point_y.append( (float(paths[num][i][1])+float(paths[num][i][1])+1.0)*0.1 )

    fig = plt.figure(figsize=(5, 5))

    ax = fig.add_subplot(111)

    for k in range(5):
        for i in range(5):
            #適宜変更（障壁個所）
            if(x[k] == 0 or x[k] == 0.8 or y[i] == 0 or y[i] == 0.8 or (x[k] == 0.6 and y[i] == 0.4)):   
                rec = pat.Rectangle(xy = (x[k], y[i]), width = 0.2, height = 0.2,
                               angle = 0, color = "black")
                ax.add_patch(rec)
            else:
                rec = pat.Rectangle(xy = (x[k], y[i]), width = 0.2, height = 0.2, fill=False, angle = 0, color = "black")
                ax.add_patch(rec)

    plt.plot(point_x, point_y, "-", linewidth=2, label="解路")
    plt.plot(point_x[0], point_y[0], "D", color="red")
    plt.plot(point_x[path_len-1], point_y[path_len-1], "x", color="blue")
    plt.show()

少し冗長的ですが、Python初心者なのでお許しを。。。

今回は5×５の迷路にしてみました。（処理量が多く、これ以上だとエラー吐かれました。。。）

そして、枠（maze[0][0~4]、maze[4][0~4]、maze[0~4][0]、maze[0~4][4]）とmaze[3][2]を障害物マスとしています。

↑こんな感じ。

結果

解1=[[1, 1], [1, 2], [1, 3], [2, 3], [3, 3]]
解2=[[1, 1], [1, 2], [2, 2], [2, 3], [3, 3]]
解3=[[1, 1], [2, 1], [2, 2], [2, 3], [3, 3]]
解4=[[1, 1], [2, 1], [2, 2], [1, 2], [1, 3], [2, 3], [3, 3]]

うんうん。なんだか良さそうですね。

絵にして見てみると、、、

解１