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

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

新規登録して質問してみよう
ただいま回答率
85.50%
コードレビュー

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

Q&A

解決済

1回答

189閲覧

Atcorderの深さ優先探索について

tomo77777

総合スコア15

コードレビュー

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

0グッド

0クリップ

投稿2020/01/26 05:31

編集2020/01/26 05:34

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

この問題について下記のコードを書きました。解答例を参考にしましたが、問題文の問題はクリアするのですが、提出してみると多くのテストケースで失敗します。

深さ優先探索を行い、探索可能な場所にtrueを格納するreachedというListを塗りつぶすことを行っています。

java

1package ari_syokyu_2_1; 2 3import java.util.ArrayList; 4import java.util.List; 5import java.util.Scanner; 6 7public class ATC001A { 8 public static int w = 0; 9 public static int h = 0; 10 public static String[][] map = null; 11 public static Boolean[][] reached = null; 12 13 public static void main(String[] args) { 14 Scanner scan = new Scanner(System.in); 15 h = Integer.parseInt(scan.next()); 16 w = Integer.parseInt(scan.next()); 17 18 map = new String[h][w]; 19 reached = new Boolean[h][w]; 20 21 List<Integer> start = new ArrayList<Integer>(); 22 List<Integer> goal = new ArrayList<Integer>(); 23 for (int i = 0; i < h; ++i) { 24 String str = scan.next(); 25 for (int j = 0; j < w; ++j) { 26 map[i][j] = str.substring(j, j + 1); 27 reached[i][j] = false; 28 if (map[i][j].equals("s")) { 29 start.add(i); 30 start.add(j); 31 } else if (map[i][j].equals("g")) { 32 goal.add(i); 33 goal.add(j); 34 } 35 } 36 } 37 38 search(start.get(0), start.get(1)); 39 40 if (reached[goal.get(0)][goal.get(1)]) { 41 System.out.println("Yes"); 42 } else { 43 System.out.println("NO"); 44 } 45 } 46 47 public static void search(int _h, int _w) { 48 if (_w < 0 || _h < 0 || w <= _w || h <= _h || map[_h][_w].equals("#")) { 49 return; 50 } 51 if (reached[_h][_w]) { 52 return; 53 } 54 55 reached[_h][_w] = true; 56 57 search(_h, _w + 1); 58 search(_h, _w - 1); 59 search(_h + 1, _w); 60 search(_h - 1, _w); 61 62 } 63 64} 65

どのあたりにバグがあるのか、教えていただきたいです。
どうぞよろしくお願いします。

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

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

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

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

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

guest

回答1

0

ベストアンサー

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

java

1 if (reached[goal.get(0)][goal.get(1)]) { 2 System.out.println("Yes"); 3 } else { 4 System.out.println("NO"); #<= "No"じゃなくて"NO"になってる 5 }

おそらくミスはここだけです。

投稿2020/01/27 16:39

yudedako67

総合スコア2047

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問