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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

1回答

2483閲覧

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

退会済みユーザー

退会済みユーザー

総合スコア0

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

0クリップ

投稿2018/09/02 05:39

編集2018/09/02 05:40

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

###問題
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 行で出力せよ。

###コード

lang

1import sys 2 3h,w = list(map(int,input().split())) 4M = [list(input()) for _ in range(h)] 5 6for i,j in enumerate(M): 7 if "s" in j: 8 sr,sc = i,j.index("s") 9 10def dfs(r,c): 11 M[r][c] = "#" 12 for i,j in ([-1,0],[1,0],[0,-1],[0,1]): 13 if not (0 <= r+i < h and 0 <= c+j < w): 14 continue 15 if M[r+i][c+j] == "g": 16 print("Yes") 17 sys.exit() 18 if M[r+i][c+j] == ".": 19 dfs(r+i,c+j) 20 21dfs(sr,sc) 22print("No")

###実行結果
コードテスト
Submission #3124726

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

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

python

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

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

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

投稿2018/09/02 05:54

編集2018/09/02 05:56
hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/09/02 06:23 編集

ご回答ありがとうございます! ご指摘のとおり追記したところ、エラーをださず正答することができました。 全く同じ質問があったとのこと、見つけられておらずお手数をかけてすみません。 Pythonではデフォルトで再帰の深度を制限しており、メモリが足りていてもその制限に達した時点でエラーとなるので、その制限を明示的に緩めてあげる必要があるということですね。 ちなみになのですが、Python3ではなくPyPy3で実行した場合、以下のとおり一部サンプルで時間制限及びメモリ制限に引っかかってしまい、全体的にも実行時間が長くなりました。 [PyPy3での実行結果](https://atc001.contest.atcoder.jp/submissions/3124909) 一般的にPyPyはPythonより速いと言われているかと思うのですが、なぜ今回の場合はPyPyの方が遅くなってしまったのか、もし分かればお教えいただけると嬉しいです! よろしくお願いします。
hayataka2049

2018/09/02 06:56

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

退会済みユーザー

2018/09/02 07:07

そうなんですね…、とりあえず今後は「再帰はCPython」の方針でやってみます。 ちなみに質問した後で以下のサイトを見つけたのですが、PyPyではsys.setrecursionlimit() を記述してもしなくても変わらないようですね。(リンクの貼り方わからずすみません) https://pypyja.readthedocs.io/en/latest/cpython_differences.html 「sys.setrecursionlimit() はPyPyでは(不要であり、)無視されます。 CPythonでは、コールのネスト数の最大値を設定します。 これを超えると実行エラーが起こります。 PyPyで他の実行エラーが原因でスタックがオーバーフローし、制限はより低レベルで チェックされます。 (制限は現在768KBでハードコードされ、Linux上では大体1480 Python callに相当します。)」 ありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問