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
どのあたりにバグがあるのか、教えていただきたいです。
どうぞよろしくお願いします。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。