蟻本 P.37 迷路の最短路を解く

まず俺BFSやったことないんだよなぁ...

→本読む　理解

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
  
  public static final int Inf = 999999999;
  public static int N = 0;
  public static int M = 0;
  public static int sx = 0;
  public static int sy = 0;
  public static int gx = 0;
  public static int gy = 0;
  public static char maze[][] = new char[N][M];
  public static int d[][] = new int[N][M];
  public static final int[] vx = {1,0,-1,0};
  public static final int[] vy = {0,1,0,-1};

  
  static class Pair{
    public int first;
    public int last;
    public Pair(int x, int y) {
      first = x;
      last = y;
    }
  }
  
  static int bfs() {
    Queue <Pair> queue = new ArrayDeque<Pair>();
    
    queue.add(new Pair(sx,sy));
    d[sy][sx] = 0;
    IN:while(!queue.isEmpty()) {
      Pair p = queue.poll();
      for(int i = 0; i < 4; i++) {
        int lx = p.first + vx[i];
        int ly = p.last + vy[i];
        
        if(lx >= 0 && lx < M  && ly >= 0 && ly < N && d[ly][lx] == Inf && maze[ly][lx] != '#') {
          d[ly][lx] = d[p.last][p.first]+1;
          if(lx == gx && ly == gy) {
            break IN;
          }
          queue.add(new Pair(lx,ly));
        }

      }

    }
    return d[gy][gx];
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    N = stdIn.nextInt();
    M = stdIn.nextInt();
    maze = new char[N][M];
    d = new int[N][M];
    
    for(int i = 0; i < N; i++) {
      String k = stdIn.next();
      for(int j = 0; j < k.length(); j++) {
        maze[i][j] = k.charAt(j);
        if(k.charAt(j) == 'S') {
          sx = j;
          sy = i;
        }
        if(k.charAt(j) == 'G') {
          gx = j;
          gy = i;
        }
      }
    }
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++) {
        d[i][j] = Inf;
      }
    }
    int c = bfs();
    System.out.println(c);
    
    }
  }
}