質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.80%

pythonで深さ優先探索

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 408

score 7

問題文

深さ優先探索の問題です

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

https://atcoder.jp/contests/atc001/tasks/dfs_a

発生している問題・エラーメッセージ

atcoderで提出するといくつかREが出ます。入力例ではすべてACなのでどうしてエラーなのか分かりません。

code

import numpy as np
import sys

h,w = map(int, input().split())
c = [list(input()) for i in range(h)]
c = np.array(c)
c = np.pad(c, 1, 'constant') #周辺を壁の代わりに0で囲う


def search(x,y):
  if c[x][y] == '#' or c[x][y] == '0':
    return #壁または外周だったら戻る
  elif c[x][y] == 'g':
    print('Yes')
    sys.exit()
  else:
    c[x][y] = '#'
    search(x+1, y)
    search(x-1, y)
    search(x, y+1)
    search(x, y-1)

s = np.argwhere(c=='s') #スタート地点を探す
search(s[0][0], s[0][1])
print('No')

試したこと

search(x-1, y)を消すとREではなくWAがでました。

補足情報(FW/ツールのバージョンなど)

手がかりがなく困っています。誤っている箇所がわかる方、Atcoder Typical Condest 001 のサンプルコードのサイトがわかる方がいらっしゃいましたら宜しくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

check解決した方法

0

再帰の上限というものがあり、それに引っかかていたようです。
sys.setrecursionlimit
を最初に記載したら通りました。
ご回答くださった方ありがとうございました。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

通った経路を塀(#)に書き換えながら探索してますが、途中で失敗したとき、
バックトラックで高橋君の位置は戻るものの、書き換えた塀を道に戻していません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2021/02/20 12:35

    ご回答ありがとうございます。こちらのブログを参考にコードを書いてみたのですが、参考にしたコードでも書き直しは行っていないように見受けられます。私のものと何が違うのでしょうか。
    https://nashidos.hatenablog.com/entry/2020/01/04/234842#%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%81%A7%E5%AE%9F%E8%A3%85

    import sys
    sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
    h,w = map(int,input().split())
    c = [list(input()) for i in range(h)]

    def dfs(x,y):
    if not(0 <= x < h) or not(0 <= y < w) or c[x][y] == "#": # 壁に当たったり、探索範囲外になった場合はreturn
    return
    if c[x][y] == "g": # ゴールを見つけたら”Yes”を出力して終了
    print("Yes")
    sys.exit()

    c[x][y] = "#" #探索済みを示すためのマーキング
    dfs(x+1,y)
    dfs(x-1,y)
    dfs(x,y+1)
    dfs(x,y-1)

    for i in range(h):
    for j in range(w):
    if c[i][j] == "s":
    sx, sy = i, j # スタート位置

    dfs(sx, sy)
    print("No")

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.80%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る