深さ優先探索
AtCoder Typical Contest 001 A - 深さ優先探索
AtCoderの問題のなかで深さ優先探索に関する問題を解きました。深さ優先探索 (Depth First Search) は、グラフの探索アルゴリズムです。
この問題は迷路のスタートからゴールまでの道があるかどうかという問題です。
迷路を解くアルゴリズムで幅優先探索を使ったことがありますが、深さと幅の違いは、スタックを使うかキューを使うかの違いです。
参考として、次のサイトを載せます。 qiita.com
コード
import java.awt.Point; import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class ProblemA2 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int H = scan.nextInt(); int W = scan.nextInt(); String [][]c = new String[H][W]; String []s = new String[H]; for(int i = 0; i < H; i++) { s[i] = scan.next(); } int sx = 0; int sy = 0; int gx = 0; int gy = 0; for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { c[i][j] = s[i].substring(j, j + 1); if(c[i][j].equals("s")) { sx = j; sy = i; } if(c[i][j].equals("g")) { gx = j; gy = i; } } } scan.close(); int state[][] = new int[H][W]; for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { if(c[i][j].equals("#")) { state[i][j] = 2; }else { state[i][j] = 0; } } } Point start = new Point(sx, sy); Deque<Point> stack = new ArrayDeque<Point>(); stack.push(start); int []dx = {1, -1, 0, 0}; int []dy = {0, 0, 1, -1}; while(!stack.isEmpty()) { Point temp = stack.pop(); int tempX = (int)temp.getX(); int tempY = (int)temp.getY(); state[tempY][tempX] = 1; for(int i = 0; i < 4; i++) { int nextX = tempX + dx[i]; int nextY = tempY + dy[i]; if(nextX >=0 && nextY >= 0 && nextX < W && nextY < H) { if(nextX == gx && nextY == gy) { System.out.println("Yes"); System.exit(0); } if(state[nextY][nextX] == 0) { state[nextY][nextX] = 1; stack.push(new Point(nextX, nextY)); //System.out.println(nextX + " : " + nextY); } } } } System.out.println("No"); } }