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

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

ただいまの
回答率

87.59%

スタックオーバーフローを回避したい

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 4,559
退会済みユーザー

退会済みユーザー

深さ優先探索アルゴリズムを再帰を用いて記述してみたのですが、プロコンサイトでの判定が一部サンプルデータで実行時エラーとなり、スタックオーバーフローが発生しているのではないかと思われます。問題点及び解決方法をご教示いただけると助かります。

問題

Atcoder Typical Contest 001 A

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

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

[入力]
入力は以下の形式で標準入力から与えられる。

H W
c0,0 c0,1 c0,W−1
c1,0 c1,1 c1,W−1
:
cH−1,0 cH−1,1 cH−1,W−1
1 行目には、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
2 行目からの H 行には、格子状の街の各区画における状態 ci,j(0≦i≦H−1,0≦j≦W−1) が与えられる。
i 行目 j 文字目の文字 ci,j はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
"s" : その区画が家であることを表す。
"g" : その区画が魚屋であることを表す。
"." : その区画が道であることを表す。
"#" : その区画が塀であることを表す。
高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
与えられた街の外を通ることはできない。
s と g はそれぞれ 1 つずつ与えられる。

[出力]
塀を 1 回も壊さずに、家から魚屋まで辿り着くことができる場合は Yes、辿りつけない場合は No を標準出力に 1 行で出力せよ。

コード

import sys

h,w = list(map(int,input().split()))
M = [list(input()) for _ in range(h)]

for i,j in enumerate(M):
    if "s" in j:
        sr,sc = i,j.index("s")

def dfs(r,c):
    M[r][c] = "#"
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
        if not (0 <= r+i < h and 0 <= c+j < w):
            continue
        if M[r+i][c+j] == "g":
            print("Yes")
            sys.exit()
        if M[r+i][c+j] == ".":
            dfs(r+i,c+j)

dfs(sr,sc)
print("No")

実行結果

 コードテスト Submission #3124726

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

0

厳密にはスタックオーバーフローではないのですが、だいたいその認識で良いと思います。

pythonは再帰の深度を制限しています。デフォルトは1000です。

上限は以下のコードで変更できます。

import sys
sys.setrecursionlimit(適当な数字)

この間、同じ質問に回答していました・・・

Python 3.x - 深さ優先探索の問題でREが出てしまう(139765)|teratail

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/09/02 15:20 編集

    ご回答ありがとうございます!
    ご指摘のとおり追記したところ、エラーをださず正答することができました。
    全く同じ質問があったとのこと、見つけられておらずお手数をかけてすみません。

    Pythonではデフォルトで再帰の深度を制限しており、メモリが足りていてもその制限に達した時点でエラーとなるので、その制限を明示的に緩めてあげる必要があるということですね。

    ちなみになのですが、Python3ではなくPyPy3で実行した場合、以下のとおり一部サンプルで時間制限及びメモリ制限に引っかかってしまい、全体的にも実行時間が長くなりました。
    [PyPy3での実行結果](https://atc001.contest.atcoder.jp/submissions/3124909)
    一般的にPyPyはPythonより速いと言われているかと思うのですが、なぜ今回の場合はPyPyの方が遅くなってしまったのか、もし分かればお教えいただけると嬉しいです!
    よろしくお願いします。

    キャンセル

  • 2018/09/02 15:56

    よくわかりません。
    軽くコードテストで触ってみた感じだと、PyPy3は今回のような再帰しまくるコードでは論外クラスで遅いみたいです。PyPy2は多少マシになるようですが(今回のコードだとinputをraw_inputにすればそのまま動くと思います)、それでもCPythonに負けてるような。
    なんででしょうね。

    キャンセル

  • 2018/09/02 16:07

    そうなんですね…、とりあえず今後は「再帰はCPython」の方針でやってみます。
    ちなみに質問した後で以下のサイトを見つけたのですが、PyPyではsys.setrecursionlimit() を記述してもしなくても変わらないようですね。(リンクの貼り方わからずすみません)

    https://pypyja.readthedocs.io/en/latest/cpython_differences.html
    「sys.setrecursionlimit() はPyPyでは(不要であり、)無視されます。 CPythonでは、コールのネスト数の最大値を設定します。 これを超えると実行エラーが起こります。 PyPyで他の実行エラーが原因でスタックがオーバーフローし、制限はより低レベルで チェックされます。 (制限は現在768KBでハードコードされ、Linux上では大体1480 Python callに相当します。)」

    ありがとうございました!

    キャンセル

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

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

関連した質問

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