TopCoder WalkingHome – SRM 222 Div 1

https://community.topcoder.com/stat?c=problem_statement&pm=3444&rd=5868

	Johnny has to walk home from school, and wants to map out the best route to take, so that he has to cross as few streets as possible. You are given a String[] map that maps the roadway layout of Johnny's town. The location of Johnny's school is designated with a 'S' character, and the location of Johnny's home is designated with a 'H' character. North-South roads are denoted by a '|' character, while East-West roads are denoted by a '-' character. Intersections, which can never be crossed, are indicated by '*' characters. Fences, indicated by a 'F' character, can also never be crossed. All other areas are indicated by '.' characters; Johnny can walk freely over these areas. For maximum safety, Johnny may only walk directly across a road, perpendicular to the traffic, never diagonally. All of Johnny's movements, onto and off of a road, and walking around town, should be in one of the four cardinal directions. Johnny may, however, cross roads that are multiple lanes wide, and doing so only counts as a single crossing. Two or more adjacent || characters are always considered to be a single road, and this works similarly for '-' characters that appear adjacent vertically. For instance, the following requires only a single crossing, since it's a single two-lane road: S.||.H Also, a situation such as the following leaves Johnny with no safe way to walk home, since he cannot cross the road diagonally, and can only step onto and off a road in a direction perpendicular to the road: S|| ||H Also notice that because Johnny can never move diagonally, in the following case, Johnny cannot get home: S.F .F. F.H You are to return an int indicating the fewest number of times Johnny must cross the street on his way home. If there is no safe way for Johnny to get home, return -1.
Definition
	Class: WalkingHome Method: fewestCrossings Parameters: String[] Returns: int Method signature: int fewestCrossings(String[] map) (be sure your method is public)
Notes
-	If a street is more than one unit wide, it still only counts as a single crossing.
Constraints
-	map will contain between 1 and 50 elements, inclusive.
-	Each element of map will contain between 1 and 50 characters, inclusive.
-	Each element of map will contain only the characters '.', '-', '|', '*', 'F', 'S', 'H'.
-	There will be exactly one occurrence each of 'S' and 'H' in map.
-	Each element of map will contain the same number of characters.
Examples
0)
	{"S.|..", "..|.H"} Returns: 1 Here, Johnny lives right across the street from the school, so inevitably, he's crossing the street once to get home.
1)
	{"S.|..", "..|.H", "..|..", "....."} Returns: 0 Similar to above, but since the road has a dead end (maybe even a cul-de-sac at the end), Johnny can get home without actually having to cross the road.
2)
	{"S.||...", "..||...", "..||...", "..||..H"} Returns: 1 Notice here that even though it's a 2-lane highway, it only counts as a single crossing.

https://github.com/livingstonese/topcoder/blob/master/src/main/java/srm222/division1/WalkingHome.java
https://github.com/rdiachenko/black-box/blob/master/topcoder/java/com/github/rd/blackbox/topcoder/WalkingHome.java
public int fewestCrossings(String[] map) {
  int n = map.length;
  int m = map[0].length();
  char[][] field = new char[n][m];
  int[] source = new int[2];
  int[] target = new int[2];
  init(map, field, source, target);

  int[][] queue = new int[n * m * 10][2];
  int[][] crossings = initCrossings(n, m);
  int head = 0;
  int tail = 1;
  queue[head][X] = source[X];
  queue[head][Y] = source[Y];
  crossings[source[X]][source[Y]] = 0;

  while (tail > head) {
    int i = queue[head][X];
    int j = queue[head][Y];
    int currentCrossings = crossings[i][j];
    ++head;

    for (int[] next : getNeighbours(i, j, field, n, m)) {
      int cost = ((field[i][j] == '.' || field[i][j] == 'S')
          && (field[next[X]][next[Y]] == '-' || field[next[X]][next[Y]] == '|')) ? 1 : 0;
      int nextCrossings = crossings[next[X]][next[Y]];

      if (nextCrossings == -1 || nextCrossings > currentCrossings + cost) {
        queue[tail][X] = next[X];
        queue[tail][Y] = next[Y];
        crossings[next[X]][next[Y]] = currentCrossings + cost;
        ++tail;
      }
    }
  }
  return crossings[target[X]][target[Y]];
}

private void init(String[] map, char[][] field, int[] source, int[] target) {
  for (int i = 0; i < map.length; i++) {
    for (int j = 0; j < map[0].length(); j++) {
      field[i][j] = map[i].charAt(j);

      if (field[i][j] == 'S') {
        source[X] = i;
        source[Y] = j;
      } else if (field[i][j] == 'H') {
        target[X] = i;
        target[Y] = j;
      }
    }
  }
}

private int[][] initCrossings(int n, int m) {
  int[][] visited = new int[n][m];

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      visited[i][j] = -1;
    }
  }
  return visited;
}

private List<int[]> getNeighbours(int i, int j, char[][] field, int n, int m) {
  int[] is = { -1, 0, 1, 0 };
  int[] js = { 0, 1, 0, -1 };
  List<int[]> neighbours = new ArrayList<>();

  for (int k = 0; k < is.length; k++) {
    int nexti = i + is[k];
    int nextj = j + js[k];

    if (isValid(is[k] == 0, i, j, nexti, nextj, field, n, m)) {
      neighbours.add(new int[] { nexti, nextj });
    }
  }
  return neighbours;
}

private boolean isValid(boolean horizontal, int i, int j, int nexti, int nextj, char[][] field, int n, int m) {
  return nexti >= 0 && nexti < n
      && nextj >= 0 && nextj < m
      && field[nexti][nextj] != 'F'
      && field[nexti][nextj] != '*'
      && ((horizontal && field[i][j] != '-' && field[nexti][nextj] != '-')
      || (!horizontal && field[i][j] != '|' && field[nexti][nextj] != '|'));
}