Advertisement
Guest User

Untitled

a guest
May 20th, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.58 KB | None | 0 0
  1. import java.util.*;
  2. import java.awt.Point;
  3. public class Main{
  4. public static void main(String[] args){
  5. Scanner sc = new Scanner(System.in);
  6.     // 右左上下を見るための配列生成
  7. int dx[] = {0, 1, 0, -1};
  8. int dy[] = {1, 0, -1, 0};
  9.  
  10. int h = sc.nextInt();
  11. int w = sc.nextInt();
  12. char map[][] = new char[h][w];
  13.  
  14. //その場所に行ったことがあるかどうかをメモする配列
  15. boolean memo[][] = new boolean[h][w];
  16. int sx = 0;
  17. int sy = 0;
  18. int gx = 0;
  19. int gy = 0;
  20.  
  21. for(int i=0; i<h; i++){
  22. map[i] = sc.next().toCharArray();
  23. for(int j=0; j<w; j++){
  24.  
  25. // startとgoalの座標を保存する。
  26. if(map[i][j]=='s'){
  27. sx = j;
  28. sy = i;
  29. }else if(map[i][j]=='g'){
  30. gx = j;
  31. gy = i;
  32. }
  33. }
  34. }
  35.  
  36. // スタック生成
  37. Deque<Point> stack = new ArrayDeque<Point>();
  38.  
  39. // Pointオブジェクトを生成しスタックにいれる。
  40. // オブジェクトを生成することでxとy両方の情報を保持することができる。
  41. stack.addFirst(new Point(sx,sy));
  42.  
  43. // startは行くことを許されているのでTrueとしてメモする。
  44. memo[sy][sx] = true;
  45.  
  46. // スタックが空になるまで繰り返す。
  47. while(!stack.isEmpty()){
  48.  
  49.        //スタックに入れた要素を取り出すし、pに入れる。
  50. Point p = stack.removeFirst();
  51.        
  52. // 4方向を見てみる。(実際にトレースしてみるとわかります。)
  53. for(int i=0; i<4; i++){
  54. int x = p.x + dx[i];
  55. int y = p.y + dy[i];
  56.  
  57. // 4方向を見て、マップ外だったらエラーが出るのでケアする。
  58. if(x>=0 && x<w && y>=0 && y<h){
  59.  
  60. // 壁ではない。かつ今の場所のメモがfalseのとき
  61. if(map[y][x]!='#' && !memo[y][x]){
  62.              // 今の場所をスタックに入れる。
  63. stack.addFirst(new Point(x,y));
  64.              // 今の場所は行けるのでTrueとメモする。
  65. memo[y][x] = true;
  66. }
  67. }
  68. }
  69. }
  70.     // goalのメモをみてTrue(行ける)ならYes‼
  71. if(memo[gy][gx]){
  72. System.out.println("Yes");
  73. }else{
  74. System.out.println("No");
  75. }
  76. }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement