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

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

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

810閲覧

pythonで深さ優先探索

Mmaple

総合スコア7

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2021/02/20 01:50

編集2021/02/20 01:53

問題文

深さ優先探索の問題です

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

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

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

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

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

code

python

1import numpy as np 2import sys 3 4h,w = map(int, input().split()) 5c = [list(input()) for i in range(h)] 6c = np.array(c) 7c = np.pad(c, 1, 'constant') #周辺を壁の代わりに0で囲う 8 9 10def search(x,y): 11 if c[x][y] == '#' or c[x][y] == '0': 12 return #壁または外周だったら戻る 13 elif c[x][y] == 'g': 14 print('Yes') 15 sys.exit() 16 else: 17 c[x][y] = '#' 18 search(x+1, y) 19 search(x-1, y) 20 search(x, y+1) 21 search(x, y-1) 22 23s = np.argwhere(c=='s') #スタート地点を探す 24search(s[0][0], s[0][1]) 25print('No')

試したこと

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

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

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

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

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

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

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

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

guest

回答2

0

自己解決

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

投稿2021/02/20 03:44

Mmaple

総合スコア7

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

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

0

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

投稿2021/02/20 03:11

sigsegv

総合スコア895

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

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

Mmaple

2021/02/20 03: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")
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問