AOJ0558 探索問題に関して

競技プログラミングの問題に関して何故間違っているのか,ご指摘していただけると幸いです.

問題文はこちら(https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558)です.(AOJ 0558 Cheese)

私の考えたアルゴリズムとしては,全探索で
食べられるチーズを探すような形になります.
またチーズを食べたらvisitedのlistを初期化することで余計な探索を避けます.

しかし,私の書いたコードでは最短stepでvisitedの関数がFalseであって欲しい時にTrueになってしまっているため,うまく最短経路を求めることができない状態となってしまいました.

visitedの更新の仕方に間違いがあると思うのですが,自分の添削上ミスを発見できなかったためご教授していただけると幸いです.

Python
1h,w,n=map(int,input().split())
2city=[list(input()) for _ in range(h)]
3
4dx=[0,0,1,-1]
5dy=[1,-1,0,0]
6
7for y in range(h):
8    for x in range(w):
9        if city[y][x]=='S':
10            sx,sy=x,y
11            city[y][x]='.'
12            break
13
14lst=[]
15visited=[[False for _ in range(h)] for _ in range(w)]
16
17def bfs(x,y,hp,step):
18    """
19    現在地(x,y)から体力hpのネズミが探索を始める.
20    食べ終わった場所の工場は.に変換する
21    また,食べれるのなら食べた方が早いため,食べることにする.
22    nを食べ終わったら終わり
23    visitedも保管して,hpに変更があった場合初期化を加える.
24    """
25    global visited
26    global lst
27    if (x<0 or w<=x) or (y<0 or h<=y):
28        return 0
29    if visited[x][y]:
30        return 0
31    
32    visited[x][y]=True
33
34    if city[y][x]=='X':
35        return 0
36    elif city[y][x]=='.':
37        tmp_visited=visited
38        print(tmp_visited)
39        for i in range(4):
40            nx,ny=x+dx[i],y+dy[i]
41            bfs(nx,ny,hp,step+1)
42            visited=tmp_visited
43        return 0
44    else:
45        if int(city[y][x])<=hp:
46            if int(city[y][x])==n:
47                lst.append(step)
48                return 0
49            tmp_city=city[y][x]
50            tmp_visited=visited
51            city[y][x]='.'
52            visited=[[False for _ in range(h)] for _ in range(w)]
53            visited[x][y]=True
54            tmptmpvisited=visited
55            for i in range(4):
56                nx,ny=x+dx[i],y+dy[i]
57                bfs(nx,ny,hp+1,step+1)
58                visited=tmptmpvisited
59            city[y][x]=tmp_city
60            visited=tmp_visited
61            return 0
62        else:
63            tmp_visited=visited
64            for i in range(4):
65                nnx,nny=x+dx[i],y+dy[i]
66                bfs(nnx,nny,hp,step+1)
67                visited=tmp_visited
68            return 0
69
70bfs(sx,sy,1,0)
71
72print(min(lst))

また,そもそものアルゴリズムの考え方として,次に食べるチーズは決まっているため,にN回全探索を行いそれぞれで最短経路を考えるように設定した方が計算量が小さくなるため今回考えたアルゴリズムは完璧なアルゴリズムでは無いものですが,こちらの考え方でも十分解けると考えたためこのアルゴリズムに関してご教授していただけると幸いです.

よろしくお願いいたします.

行動規範の内容に同意します

回答1件

ベストアンサー

tmp_visited=visited で待避し,visited=tmp_visited で戻したつもりになっているけれども実際はそうなっていないことが問題でしょう。

python
1>>> A = [1]
2>>> B = A
3>>> B.clear()
4>>> B.append(4)
5>>> A = B
6>>> print(A)
7[4]

となることの意味を考えてください。

defとListの関係についても参照してください。

投稿2021/03/21 09:46

ppaul

総合スコア24666

unser

2021/03/21 11:14

ご回答いただきありがとうございます. もし参照先を変更し新しいものを作成する場合は import copyとし,copy.deepcopy()を使用する必要があることを知りました. また,その場合分岐が多くなることに加えてメモリや計算量を考えるとよく無いため幅優先探索を行うことやvisitedの代わりに初期設定をINFとした distanceとしてに距離を保管しておくことが大事であると感じました.

行動規範の内容に同意します